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