#include <stdio.h>
#include <stdlib.h>
#define MAXN 2000000
#define MOD 9999991

inline int legendre(int p, int n){
  int rez=n/p, d=p;
  while(1LL*d*p<=n){
    d*=p;
    rez+=n/d;
  }
  return rez;
}

void euclid(int a, int b, int* x, int* y){
  if(b==0){
    (*x)=1; (*y)=0;
  } else{
    int x0, y0;
    euclid(b, a%b, &x0, &y0);
    (*x)=y0;
    (*y)=x0-(a/b)*y0;
  }
}

inline int mypow(int b, int e){
  int rez=1;
  while(e){
    if(e&1)
      rez=(1LL*rez*b)%MOD;
    b=(1LL*b*b)%MOD;
    e>>=1;
  }
  return rez;
}

char ciur[MAXN+1];

int main()
{
    FILE *fin, *fout;
    int n, i, d, e1, e2, put;
    int rez;
    fin=fopen("dirichlet.in", "r");
    fscanf(fin, "%d", &n);
    fclose(fin);
    for(i=2; i*i<=2*n; i++)
      if(ciur[i]==0)
        for(d=i*i; d<=2*n; d+=i)
          ciur[d]=1;
    rez=1LL;
    for(i=2; i<=2*n; i++)
      if(ciur[i]==0)
        rez=(1LL*rez*mypow(i, legendre(i, 2*n)-2*legendre(i, n)))%MOD;
    euclid(n+1, MOD, &i, &d);
    i=i>=0?i:MOD+i%MOD;
    fout=fopen("dirichlet.out", "w");
    fprintf(fout, "%d\n", (1LL*i*rez)%MOD);
    fclose(fout);
    return 0;
}