#include <iostream>
#include <fstream>
#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 gcd(int a, int b) {
     int x = 0, lastx = 1;
     int y = 1, lasty = 0;

     while(b != 0) {
          int aux = a / b;

          int jeg = b;
          b = a % b;
          a = jeg;

          jeg = x;
          x = lastx - aux * x;
          lastx = jeg;

          jeg = y;
          y = lasty - aux * y;
          lasty = jeg;
     }

     return lastx;
}

int main() {
     fstream f1, f2;
     f1.open("dirichlet.in", ios::in), f2.open("dirichlet.out", ios::out);
     int i, j, p, q;

     f1>>N;

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

     f2<<sol<<'\n';

     f1.close(); f2.close();
     return 0;
}