program circlex;
var
  j,i,n:integer;
  a:array [1..1000] of int64;
begin
  fillchar (a,sizeof(a),0);
  assign (input,'circlex.in');
  reset (input);
  readln (n);
  close (input);
  assign (output,'circlex.out');
  rewrite (output);
  a[1]:=1;a[2]:=1;a[3]:=3;
  for i:=4 to n do begin
    a[i]:=((i-1)*i) div 2+1;
    j:=i div 2;
    while j<>1 do begin
      a[i]:=a[i]+2*a[j];
      j:=j div 2;
    end;
    if i mod 2<>0 then inc(a[i],a[i div 2+1]);
  end;
  writeln (a[n] mod 12345);
  close (output);
end.