#include <fstream>

using namespace std;
const int MOD = 9999991;

ifstream f("dirichlet.in");
ofstream g("dirichlet.out");

long long power(long long x, int n)
{
    long long val = 1;
    while(n)
    {
        if(n % 2 == 1)
            val = val * x % MOD;
        x = x * x % MOD;
        n /= 2;
    }
    return val;
}

inline long long InvMod(int x)
{
    return power(x, MOD - 2);
}

long long Catalan(int n)
{
    long long fact1 = n + 1, fact2 = 1;
    for (int i = 2; i <= n; i++)
    {
        fact1 = fact1 * (n + i) % MOD;
        fact2 = fact2 * i % MOD;
    }
    fact2 = fact2 * (n + 1) % MOD;
    return fact1 * InvMod(fact2) % MOD;
}

int main()
{
    int N;
    f >> N;
    g << Catalan(N);
    f.close();
    g.close(); 
    return 0;
}