#include <stdio.h>
#define modulo 9999991

int stiva[1000005];

int main(){
  FILE *fin=fopen("dirichlet.in","r");
  FILE *fout=fopen("dirichlet.out","w");
  int n;
  fscanf(fin,"%d",&n);
  int loc;
  int i;
  for(i=1;i<=n;i++)stiva[i]=-1;
  loc=1;
  long long sol=0;
  int suma=0;
  while(loc>=1){
    if(loc==n && suma==n && stiva[n]!=0 && stiva[n]!=-1){
      //tiparesc solutia
      /*for(i=1;i<=n;i++)
        fprintf(fout,"%d ",stiva[i]);
      fprintf(fout,"\n");*/
       sol++;
       sol=sol%modulo;
    }
    stiva[loc]++;
    if(stiva[loc])suma++;
    if(suma>loc || loc>n){
       suma-=stiva[loc];
       stiva[loc]=-1;
       loc--;
    }else loc++;
}
    fprintf(fout,"%lld ",sol);
   
return 0;
}