Program cutii;
var t,u: array[0..800000] of int64;{longint}
    cu,ct, i,j,k,n : longint;
    r: int64;            {int64}
    f1,f2: text;

BEgin
     assign(f1, 'dirichlet.in');
     assign(f2, 'dirichlet.out');
     reset(f1);
      readln(f1,n);
      close(f1);
      t[1]:=1; ct:=1;
      for i:=1 to n -1 do
          Begin
               for j:=1 to ct do
                        for k:=2 to t[j]+1 do
                            Begin
                                 inc(cu);
                                 u[cu]:=k;
                            end;
               for j:=1 to cu do
                   t[j]:=u[j];
                   ct:=cu; cu:=0;
          end;
      for i:=1 to ct do
          r:=r+t[i];
      rewrite(f2);
      writeln(f2,r mod 9999991);
      close(f2);
end.