#include <bits/stdc++.h>
using namespace std;

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

const int MOD = 9999991;
long long C[1001];

void Catalan(int n)
{
    C[0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= i; j++)
            C[i] = (C[i] + 1LL * C[j - 1] * C[i - j]) % MOD;
    }
}

int main()
{
    int n;
    f >> n;
    Catalan(n);
    g << C[n];
    return 0;
}