#include <iostream>
#include <fstream>
#define i64 long long

using namespace std;

i64 mod = 9999991;

i64 put(i64 N, i64 P)
{
    i64 rez = 1;
    while(P)
    {
        if(P & 1)
            rez = (rez * N) % mod;
        N = (N * N) % mod;
        P >>= 1;
    }
    return rez;
}

int main()
{
    ifstream in ("dirichlet.in");

    i64 N, val, C, i, F = 1;
    in >> N;
    for(i = 1, val = 1; i < N; i++)
    {
        C = ( (i << 1) + 1) << 1;
        val = (val * C) % mod;
        F = (F * (i + 2)) % mod;
    }
    val = (val * put(F, mod - 2)) % mod;

    ofstream out("dirichlet.out");
    out << val;
    return 0;
}