#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 100
#define mod 9999991
#define LL long long

int N, sol = 1;
int V[maxn];

void back(int niv, int ram) {
    if(niv == N + 1) {
         int i, s = 0, ok = 1;
         for(i=1; i<=N; i++) {
              s += V[i];
              if(s > i) {
                   ok = 0;
                   break;
              }
         }

         if(ok && s == N) {
              sol ++;
         }
    }
    else {
         int i;
         for(i=0; i<=ram; i++) {
              V[niv] = i;
              back(niv+1, ram-i);
         }
    }
}

int x, y, aux;

void gcd(int a, int b) {
     if(!b) x = 1, y = 0;
     else {
         gcd(b, a % b);
         aux = x;
         x = y;
         y = aux - y * (a / b);
     }
}

int main() {
     FILE *f1=fopen("dirichlet.in", "r"), *f2=fopen("dirichlet.out", "w");
     int i, j, p, q;

     fscanf(f1, "%d\n", &N);

     /**
     for(i=N+2; i<=2*N; i++) {
          sol = ((LL)sol * i) % mod;
     }

     for(i=2; i<=N; i++) {
          LL inv = 0, ins;
          gcd(inv, ins, i, mod);
          if(inv <= 0) {
               inv = mod + inv % mod;
          }
          sol = ((LL)sol * inv) % mod;
     }
     **/

     sol = 1;
     for(i=1; i<=N; i++) {
          int aux = sol;
          sol = ((LL)2 * (2*i-1) * aux) % mod;
          //int inv = 0, ins;
          //gcd(inv, ins, i+1, mod);
          x = y = 0;
          gcd(i+1, mod);
          if(x <= 0) {
               x = mod + x % mod;
          }
          sol = ((LL)sol * x) % mod;
     }

     fprintf(f2, "%d\n", sol);

     fclose(f1); fclose(f2);
     return 0;
}