program elysian;
const
fin='zbfa.in';fout='zbfa.out';
var
n:longint;
f:array[0..1000] of longint;
f1:text;

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

procedure init;
begin
assign(f1,fin);reset(f1);
readln(f1,n);
close(f1);
end;

begin
init;
assign(f1,fout);rewrite(f1);
f[0]:=1;
f[1]:=3;
dp;
writeln(f1,f[n]);
close(f1);
end.