program ex1;
 var
    n,i,j,a,b,ans:integer;

 function C(n,m:integer):int64;
  var
     tmp:longint;
     i,j:integer;
  begin
   tmp:=1;
   for i:=m+1 to n do
   tmp:=tmp*i;
   for j:=2 to n-m do
   tmp:=tmp div j;
   exit(tmp mod 12345);
  end;


 begin
  assign(input,'circlex.in');
  assign(output,'circlex.out');
  reset(input); rewrite(output);
  read(n);
  for i:=1 to n div 2 do
   begin
   a:=i;
   b:=n-a;
   if a>b
   then ans:=(ans+C(a,b)) mod 12345
   else ans:=(ans+C(b,a)) mod 12345;
   end;
  writeln((ans*n div 2+1) mod 12345);
  close(input); close(output);
 end.