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

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