#include <fstream>
using namespace std;
const int MOD = 9999991;
ifstream f("dirichlet.in");
ofstream g("dirichlet.out");
int putere(int x, int m)
{
    int val = 1;
    while(m > 0)
    {
        if(m & 1)
            val = 1LL * val * x % MOD;
        x = 1LL * x * x % MOD;
        m >>= 1;
    }
    return val;
}

int catalan(int n)
{
    int c = 1;
    for(int i = 1; i < n; i++)
        c = 2LL * c * (2 * i + 1) % MOD * putere(i + 2, MOD - 2) % MOD;


    return c;
}

int main()
{
    int n;
    f >> n;
    g << catalan(n);
    return 0;
}