program yuanxian(input,output);
 var
  i,j,k:longint;
  a:array [0..1001] of longint;
  n,ans:longint;
   f1,f2:text;
begin
 assign(f1,'circlex.in');
 assign(f2,'circlex.out');
 reset(f1);
 rewrite(f2);
 readln(f1,n);
 close(f1);
 a[0]:=1;
 a[1]:=1;
  for i:=2 to n do  begin
   for j:=0 to i-2 do
    a[i]:=(a[i]+a[j]*a[i-2-j]) mod 12345;
     a[i]:=(a[i]+a[i-1]) mod 12345;
     end;
     ans:=a[n];
   writeln(f2,ans);
   close(f2);
  end.