#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);
         }
    }
}

void gcd(LL &x, LL &y, int a, int b) {
     if(!b) x = 1, y = 0;
     else {
         gcd(x, y, b, a % b);
         LL 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+1; i<=2*N; i++) {
          sol = (sol * i) % mod;
     }

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

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

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