#include <iostream>
#include <fstream>

using namespace std;
const int MOD=9999991;

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

int N;
long long C[1000001];

int main()
{
    f >> N;
    C[0]=1;
    for(int i=1;i<=N;i++)
        for(int j=0;j<i;j++)
            C[i]=(C[i]+(C[j]*C[i-j-1]))%MOD;
    g << C[N];
    return 0;
}