program ex;
type
 ss=array[0..1000]of longint;
var
 f:ss;
 n:integer;
 f1,f2:text;
procedure init;
 begin
  assign(f1,'circlex.in');
  assign(f2,'circlex.out');
  reset(f1);
  rewrite(f2);
  readln(f1,n);
  close(f1);
 end;
procedure main;
 var
  i,j:integer;
 begin
  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])mod 12345;
    f[i]:=(f[i]+f[i-1]) mod 12345;
   end;
  writeln(f2,f[n]);
 end;
begin
 init;
 main;
 close(f2);
end.