program circlex;
type
shuzu=array[0..1000] of longint;
var
i,j,k,m,n,a,b,c:longint;
s:shuzu;
f1,f2:text;
begin
assign(f1,'circlex.in');reset(f1);
assign(f2,'circlex.out');rewrite(f2);
readln(f1,n);
c:=1;
fillchar(s,sizeof(s),0);
 s[0]:=1;s[1]:=1;
for i:=2 to n do
  begin
 for j:=0 to i-2 do
   s[i]:=(s[i]+s[j]*s[i-2-j]) mod 12345;
    s[i]:=(s[i]+s[i-1]) mod 12345;
    end;
 s[n]:=s[n] mod 12345;
 writeln(f2,s[n]);
 close(f2);
 end.