#include <stdio.h>
#define modulo 9999991

int main(){
  FILE *fin=fopen("dirichlet.in","r");
  FILE *fout=fopen("dirichlet.out","w");
  int n;
  fscanf(fin,"%d",&n);
  if(n==1){
    fprintf(fout,"1\n");
    return 0;
   }
  if(n==2){
    fprintf(fout,"2\n");
    return 0;
  }
  //daca e mai mare ca 3
  int s=0,sp=3+2;
  int i;
  for(i=n-2;i>0;i--){
     s=(s+(sp*i))%modulo;
     sp=(sp+i)%modulo;
  }
  fprintf(fout,"%d\n",s);
return 0;
}