#include <iostream>
#include <fstream>

using namespace std;
const int MOD = 9999991;

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

int powlg(int baza, int exp)
{
    int rez = 1;
    while(exp > 0)
    {
        if(exp % 2 == 1)
            rez = (1LL * rez * baza) % MOD;
        baza = (1LL * baza * baza) % MOD;
        exp /= 2;
    }
    return rez;
}

inline int invers(int a)
{
    return powlg(a, MOD - 2);
}

int main()
{
    int N, i;
    fin >> N;
    /// C_n = (2n)! * invers( n! * (n+1)! )
    long long fact2N = 1,factN = 1;
    for(i = 1; i <= 2 * N; i++)
        fact2N = (fact2N * i) % MOD;
    for(i = 1; i <= N; i++)
        factN = (factN * i) % MOD;
    long long factNplus1 = (factN * (N + 1)) % MOD;
    long long num = (factN * factNplus1) % MOD;
    long long rez = (fact2N * invers(num)) % MOD;
    fout << rez;
    return 0;
}