program chashu(input,output);
 var
  i,j,k:longint;
  n:longint;
  ans:int64;
  oushu,jishu:array [1..1001] of longint;
begin
 assign(input,'chashu.in');
 assign(output,'chashu.out');
 reset(input);
 rewrite(output);
 readln(n);
 oushu[1]:=8;
 jishu[1]:=1;
  for i:=2 to n do begin
   oushu[i]:=(oushu[i-1]*9+jishu[i-1]);
   jishu[i]:=(jishu[i-1]*9+oushu[i-1]);
  end;
 ans:=(oushu[n] mod 12345);
 write(ans);
 close(input);
 close(output);
end.