program cch(input,output);
var
 f:array[0..1000,0..1000] of int64;
 n,i,j:integer;
 ans:int64;
begin
 assign(input,'chashu.in');
 assign(output,'chashu.out');
 reset(input);
 rewrite(output);
 readln(n);
 {f[1,2]:=9; f[1,1]:=1; f[0,1]:=0; f[0,2]:=0;
 for i:=2 to n do
  begin
   f[i,2]:=(f[i-1,1]+f[i-1,2]*8+f[i-2,1]+f[i-2,2]*8) mod 12345;
   f[i,1]:=(f[i-1,2]+f[i-2,2]+(f[i-1,1]+f[i-2,1])*8) mod 12345;
  end;
 write(f[n,2]);}
 f[1,0]:=8;
 for i:=2 to n do f[i,0]:=f[i-1,0]*9 mod 12345;
 for i:=1 to n do f[i,i]:=1;
 for i:=2 to n do
  for j:=1 to i-1 do
   f[i,j]:=(f[i-1,j-1]+f[i-1,j]*9) mod 12345;
 ans:=0;
 for i:=0 to n do
  if i mod 2=0 then
   inc(ans,f[n,i]);
 write(ans mod 12345);
 close(input);
 close(output);
end.