#include <fstream>
#include <set>

using namespace std;

ifstream cin("dirichlet.in");
ofstream cout("dirichlet.out");

const int MOD =  9999991;

int RaiseToPower(int base, int power) {
    int answer = 1;
    while (power) {
        if (power % 2)
            answer = (1LL * answer * base) % MOD;
        base = (1LL * base * base) % MOD;
        power /= 2;
    }
    return answer;
}

int Catalan(int n) {
    int limit = 2 * n, answer = 1, divide = 1;
    for (int i = n + 1; i <= limit; i++)
        answer = (1LL * answer * i) % MOD;
    n++;
    for (int i = 2; i <= n; i++)
        divide = (1LL * divide * i) % MOD;
    answer = (1LL * answer * RaiseToPower(divide, MOD - 2)) % MOD;
    return answer;
}

int main() {
    int n;
    cin >> n;
    cout << Catalan(n);
    return 0;
}