program circlex(input,output);
var
n,i,j:integer;
f:array[0..1000]of integer;
begin
assign(input,'circlex.in');assign(output,'circlex.out');
reset(input);rewrite(output);
readln(n);
fillchar(f,sizeof(f),0);
f[0]:=1;f[1]:=1;f[2]:=2;
for i:=3 to n do begin
f[i]:=f[i-1];
for j:=1 to i-1 do
f[i]:=(f[i]+f[j-1]*f[i-1-j])mod 12345;
end;
writeln(f[n]);
close(input);close(output);
end.