#include <fstream>

#define MOD 9999991
using namespace std;

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

typedef unsigned long long ull;

ull _pow(ull baze, ull pw){
    ull rez = 1, p = baze;
    while(pw){
        if(pw & 1){
            rez *= p;
            rez %= MOD;
        }

        p *= p;
        p %= MOD;
        pw >>= 1;
    }
    return rez;
}

int main()
{
    int n;
    fin >> n;

    ull nfact = 1, nfact2 = 1;
    for(int i = 1; i <= n; ++i)
        nfact = (nfact * i) % MOD;
    nfact2 = nfact;
    for(int i = n + 1; i <= 2 * n; ++i)
        nfact2 = (nfact2 * i) % MOD;
    ull nfact3 = (nfact * (n + 1)) % MOD;
    fout << nfact2 * _pow(nfact, MOD - 2) % MOD * _pow(nfact3, MOD - 2) % MOD << '\n';
    return 0;
}