#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("dirichlet.in");
ofstream fout("dirichlet.out");

constexpr int MOD = 9999991;

static inline int fastpow(int x, int n) {
    int ans = 1;
    for (; n; n >>= 1) {
        if (n & 1) ans = (1LL * ans * x) % MOD;
        x = (1LL * x * x) % MOD;
    }
    return ans;
}

static inline int choose(int n, int k) {
    int A = 1, B = 1;
    for (int i = 1; i <= k; ++i) {
        A = (1LL * A * (n - i + 1)) % MOD;
        B = (1LL * B * i) % MOD;
    }
    return (1LL * A * fastpow(B, MOD - 2)) % MOD;
}

static inline int catalan(int n) {
    return (1LL * choose(2 * n, n) * fastpow(n + 1, MOD - 2)) % MOD;
}

int main() {
    int n;
    fin >> n;
    fout << catalan(n);
    fin.close();
    fout.close();
    return 0;
}