#include <iostream>
#include <fstream>
using namespace std;

const int MOD = 9999991;
const int NMAX = 1000000;

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

long long fact[NMAX], inv_fact[NMAX];

long long powmod(long long b, long long e, long long m) {
    long long res = 1;
    while (e) {
        if (e & 1) res = (res * b) % m;
        b = (b * b) % m;
        e >>= 1;
    }
    return res;
}

void precalc() {
    fact[0] = 1;
    for (int i = 1; i < NMAX; ++i)
        fact[i] = (fact[i - 1] * i) % MOD;

    inv_fact[NMAX - 1] = powmod(fact[NMAX - 1], MOD - 2, MOD); // Fermat
    for (int i = NMAX - 2; i >= 0; --i)
        inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD;
}

long long comb(int n, int k) {
    if (k < 0 || k > n) return 0;
    return (((fact[n] * inv_fact[k]) % MOD) * inv_fact[n - k]) % MOD;
}

int main() {
    int n;
    fin >> n;

    precalc();

    long long C = comb(2 * n, n);
    long long catalan = (C * powmod(n + 1, MOD - 2, MOD)) % MOD;

    fout << catalan << "\n";

    return 0;
}