#include <bits/stdc++.h>

using namespace std;
ifstream fin("dirichlet.in");
ofstream fout("dirichlet.out");
typedef long long ll;
const int MOD = 9999991;
const int DIM = 2e6;
int fact[DIM + 3];

inline ll expRapida(ll A, int n) {
    ll p = 1;
    while(n) {
        if(n & 1) p = p * A % MOD;
        A = A * A % MOD, n /= 2;
    }
    return p;
}

inline void prelucru() {
    fact[0] = 1;
    for(int i=1; i<=DIM; i++) fact[i] = 1LL * fact[i - 1] * i % MOD;
}

inline ll combi(int n, int k) { return 1LL * fact[n] * expRapida(fact[k], MOD - 2) % MOD * expRapida(fact[n - k], MOD - 2) % MOD; }
inline int catalan(int n) { return combi(2 * n, n) * expRapida(n + 1, MOD - 2) % MOD; }

signed main()
{
    prelucru();
    int n; fin >> n;
    fout << catalan(n);

    return 0;
}