#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 * base % MOD;
   return 1LL * halfPower * halfPower % MOD;
}

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

int main() {
   int n;

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