program bing;
var
 n,i,j,k,t:longint;
 f1,f2:text;
 a:array[0..1000,0..1000]of longint;
begin
 assign(f1,'chashu.in');reset(f1);
 assign(f2,'chashu.out');rewrite(f2);
 read(f1,n);
 if n=1 then writeln(8)
 else
 begin
 fillchar(a,sizeof(a),0);
 a[1,0]:=8;
 for i:=2 to n do a[i,0]:=(a[i-1,0]*9)mod 12345;
 for i:=1 to n do a[i,i]:=1;
 for i:=2 to n do
 for j:=1 to i-1 do
 a[i,j]:=(a[i-1,j-1]+a[i-1,j]*9)mod 12345;
   k:=0;
  for i:=0 to n do
  if i mod 2=0 then
  k:=(k+a[n,i])mod 12345;
 writeln(f2,k mod 12345);
 close(f1);close(f2);
end;
end.