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

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

write(f2,f[n]);
close(f1); close(f2);
end.