program chashu;
var
n:integer;
x:array[1..1000,-1..1000]of longint;
max:longint;

procedure ini;
begin
assign(input,'chashu.in');
reset(input);
assign(output,'chashu.out');
rewrite(output);
readln(n);
close(input);
fillchar(x,sizeof(x),0);
max:=0;
end;

procedure main;
var
i,j:integer;
begin
x[1,0]:=8;
x[1,1]:=1;

for i:=2 to n do
 for j:=0 to i do
  x[i,j]:=(x[i-1,j-1]+x[i-1,j]*9)mod 12345;
for i:=0 to n do
 if (i mod 2=0) then max:=max+x[n,i];
end;

begin
ini;
main;
writeln(max mod 12345);
close(output);
end.