program puzhuan;
const
fin='puzhuan.in';
fou='puzhuan.out';
var
f:array[1..10000,1..2]of longint;
total,n,i:longint;
f1,f2:text;

begin
assign(f1,fin); assign(f2,fou);
reset(f1); rewrite(f2);
read(f1,n);
f[1,1]:=1; f[1,2]:=0;
f[2,1]:=1; f[2,2]:=2;
for i:=3 to n do
 begin
  f[i,1]:=(f[i-1,1]+f[i-1,2]) mod 12345;
  f[i,2]:=(2*(f[i-2,1]+f[i-2,2])) mod 12345;
 end;
total:=(f[n,1]+f[n,2]) mod 12345;
write(f2,total);
close(f1); close(f2);
end.