program elysian;
const
fin='puzhuan.in';fout='puzhuan.out';
var
n:longint;
f:array[0..10000000] of longint;
f1,f2:text;

procedure init;
var
i:longint;
begin
assign(f1,fin);reset(f1);
readln(f1,n);
close(f1);
for i:=0 to n do
f[i]:=1;
end;

procedure dp;
var
i,j:longint;
begin
for i:=1 to n do
f[i]:=(f[i-1]+f[i-2]*2) mod 12345;
end;

begin
init;
dp;
assign(f2,fout);rewrite(f2);
writeln(f2,f[n]);
close(f2);

end.