program chashu;
type
shuzu=array[1..1000,0..1000] of longint;
var
s1,s2:string;
i,j,k,m,n,ans:longint;
s:shuzu;
begin
assign(input,'chashu.in');reset(input);
assign(output,'chashu.out');rewrite(output);
readln(n);   close(input);
fillchar(s,sizeof(s),0);
s[1,0]:=8; ans:=0;
for i:=2 to n do
begin
 s[i,0]:=s[i-1,0]*9;
 s[i,0]:=s[i,0] mod 12345;
 end;
for i:=1 to n do
  s[i,i]:=1;
 for i:=2 to n do
  for j:=1 to i-1 do
    s[i,j]:=(s[i-1,j-1]+s[i-1,j]*9) mod 12345;
   for i:=0 to n do
     if i mod 2=0 then
       ans:=(ans+s[n,i]) mod 12345;
       writeln(ans);
       close(output);
end.