#include <iostream>
#include <fstream>
using namespace std;

#define ll long long
#define MOD 9999991

ll N, C;


int main()
{
    ifstream in("dirichlet.in");
    ofstream out("dirichlet.out");
    ll i;
    in >> N;
    if(N == 1) out << 1 << "\n";
    else
    {
        C = 1;
        for(i = 2; i <= N; i++)
        {
              C = C * (4 * (i - 1) + 2);
              C = (C / (i + 1));
        }
        out << C % MOD << "\n";
    }
    return 0;
}