program yuffie;
const
fin='chashu.in';fout='chashu.out';
var
f1,f2:text;
n:longint;
f:array[1..1001,0..1] of longint;

procedure dp;
var
i:longint;
begin
readln(f1,n);
close(f1);
f[1,0]:=9;
f[1,1]:=1;

for i:=2 to n do
if i<n then
  begin
  f[i,0]:=(f[i-1,0]*9+f[i-1,1])mod 12345;
  f[i,1]:=(f[i-1,0]+f[i-1,1]*9)mod 12345;
  end
else begin
  f[i,0]:=(f[i-1,0]*8+f[i-1,1])mod 12345;
  f[i,1]:=(f[i-1,0]+f[i-1,1]*8)mod 12345;
end;
end;

BEGIN
assign(f1,fin);reset(f1);
dp;
assign(f2,fout);rewrite(f2);
writeln(f2,f[n,0]);

close(f2);
END.