#include <bits/stdc++.h>

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

inline int expRapida(int A, int n) {
    int 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] = fact[i - 1] * i % MOD;
    inv[DIM] = expRapida(fact[DIM], MOD - 2);
    for(int i=DIM-1; i>=0; i--) inv[i] = inv[i + 1] * (i + 1) % MOD;
}

inline int combi(int n, int k) { return fact[n] * inv[k] % MOD * inv[n - k] % 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;
}