const mod1=9999991;
var n,i,j:longint;
    a,b:array[1..1000000]of longint;

begin
  assign(input,'dirichlet.in'); reset(input);
  assign(output,'dirichlet.out'); rewrite(output);

  read(n);

  if n = 1 then
    write('1')
  else
  begin
    for i := 1 to n do
      a[i] := i;
    for i := 2 to n do
    begin
      for j := 1 to i-1 do
        b[j] := 0;          //pune 0
      for j := i to n do
        b[j] := (a[j] + b[j-1]) mod mod1;    //completeaza linie
      for j := 1 to n do
      begin
        a[j] := b[j] ; // transfer linie
              //write(a[j],' ');
      end;
      //writeln();
    end;
    write(b[n]);
  end;




  close(input);
  close(output);
end.