#include <fstream>

using namespace std;
ifstream cin("dirichlet.in");
ofstream cout("dirichlet.out");
const int MOD = 9999991;
long long fact, inv;
long long fastpow(long long base, long long exp)
{
    long long prod = 1;
    while(exp)
    {
        if(exp&1)
            prod = prod * base % MOD;
        base = base * base % MOD;
        exp /= 2;
    }
    return prod % MOD;
}
int main()
{
    int n, i;
    cin >> n;
    fact = inv = 1;
    for(i = 1; i <= 2*n; i++)
        fact = 1LL * fact * i % MOD;
    for(i = 1; i <= n; i++)
        inv = 1LL * inv * i % MOD;
    cout << fact * fastpow(inv, MOD-2) % MOD * fastpow(inv, MOD-2) % MOD * fastpow(n+1, MOD-2) % MOD;
    return 0;
}