#include <iostream>
using namespace std;

const int MOD = 9999991;
int 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;
    cin >> n;
    Catalan(n);
    cout << C[n];
    return 0;
}