program waterfire;
const
fin='chashu.in';
fout='chashu.out';
var

ans,i,j,n,s:longint;
f,g:text;
data:array[0..1000,0..1000] of longint;

begin
assign(f,fin);reset(f);
assign(g,fout);rewrite(g);
readln(f,n);
if n=1 then writeln(g,9)
 else begin
  data[1,0]:=8;
  data[1,1]:=1;
  for i:=2 to n do  begin
  data[i,i]:=1;
  data[i,0]:=(data[i-1,0]*9) mod 12345;
   end;
   ans:=data[n,0];
   for i:=2 to n do
    for j:=1 to i-1 do begin
    data[i,j]:=(data[i-1,j-1]+data[i-1,j]*9) mod 12345;
    if (j mod 2=0)and(i=n)  then   ans:=(ans+data[i,j]) mod 12345;
    end;
    if n mod 2=0 then ans:=(ans+1) mod 12345;
    end;
    write(g,ans);
    close(f);
    close(g);
    end.