#include <iostream>
#include <fstream>

using namespace std;

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

const int MOD = 9999991;

long long pow(int b, int e, int M)
{
    long long p=1, a=b;
    for(; e; e>>=1)
    {
        if(e&1) p = (p * a) % M;
        a = (a * a) % M;
    }
    return p;
}

int euler(int n){
    int d, r;

    d = 2;
    r = n;

    while(d * d <= n){
        if(n % d == 0){
            r = r / d * (d - 1);
        }
        while(n % d == 0){
            n /= d;
        }
        d++;
    }

    if(n > 1){
        r = r / n * (n - 1);
    }

    return r;
}

int comb(int n, int k, int M){
    int c1, c2, i, p;

    c1 = 1;

    p = euler(M);

    for(i = 1; i <= k; ++i){
        c2 = (((n - i + 1) * c1) % M * pow(i, p - 1, M)) % M;
        c1 = c2;
    }
    return c1;
}

int main()
{
    int n;

    fin >> n;

    int C = comb(2 * n, n, MOD);
    int catalan = (1LL * C * pow(n + 1, MOD - 2, MOD)) % MOD;

    fout << catalan << "\n";

    fin.close();
    fout.close();
    return 0;
}