program  cir;
var
   e:text;
   f:array[0..1000] of longint;
   i,j,m,n:longint;
begin
   assign(e,'circlex.in');
   reset(e);
   readln(e,n);
   close(e);
   for i:=1 to n do
   f[i]:=0;
   f[0]:=1;
   f[1]:=1;
   for i:=2 to n do  begin
   for j:=0 to i-2 do
   f[i]:=f[i]+f[j]*f[i-2-j];
   f[i]:=f[i]+f[i-1];
   if f[i]>12345 then f[i]:=f[i] mod 12345;
   end;
   assign(e,'circlex.out');
   rewrite(e);
   writeln(e,f[n]);
   close(e);
end.