#include <fstream>

using namespace std;

ifstream in("dirichlet.in");
ofstream out("dirichlet.out");

const int MOD = 9999991;

int fastExp(int base, int exp) {
   if(exp == 0) return 1;
   int halfPower = fastExp(base, exp >> 1);
   if(exp & 1) return 1LL * halfPower * halfPower % MOD * base % MOD;
   return 1LL * halfPower * halfPower % MOD;
}

int getComb(int n, int k) {
   if(k == 0 || k == n) return 1;
   int fact = 1, firstDiv, secondDiv;
   for(int i = 1; i <= n; i++) {
      fact = 1LL * fact * i % MOD;
      if(i == k) firstDiv = fastExp(fact, MOD - 2);
      if(i == n - k) secondDiv = fastExp(fact, MOD - 2);
   }
   return 1LL * fact * firstDiv % MOD * secondDiv % MOD;
}

int main() {
   int n;

   in >> n;
   out << 1LL * getComb(2*n, n) * fastExp(n + 1, MOD - 2) % MOD << '\n';
   return 0;
}