program puzhuan;
var x1,x2:longint;
pi,po:text;
n:longint;
jg:longint;
function yunsuan(a:longint):longint;
begin
if a=1 then yunsuan:=1;
if a=2 then yunsuan:=3;
if a=3 then yunsuan:=5;
if a>3 then yunsuan:=yunsuan(a-1)+2+(yunsuan(a-2)-1)*2;
end;
begin
assign(pi,'puzhuan.in');
reset(pi);
readln(pi,n);
jg:=yunsuan(n);
assign(po,'puzhuan.out');
rewrite(po);
if jg>12345 then jg:=jg mod 12345;
writeln(po,jg);
close(pi);
close(po);
end.