#include <cstdio>
using namespace std;
const int MOD = 9999991;
const int NMAX = 1000000;
const int RAD = 1000;
bool c[NMAX + 5];
long long mypow(int a, int b){
    long long a1 = a, p = 1;
    for (; b; b >>= 1){
        if (b & 1)
            p = (p * a1) % MOD;
        a1 = (a1 * a1) % MOD;
    }
    return p;
}
int legendre(int a, int b){
    int a1 = a, ans = 0;
    while (a1 <= b){
        ans += b / a1;
        a1 *= a;
    }
    return ans;
}
long long catalan(int n, int k){
    int i, putere;
    long long ans = 1;
    for (i = 2; i <= n; i ++)
        if (!c[i]){
            putere = legendre(i, n) - legendre(i, k) - legendre(i, n - k);
            ans = (ans * mypow(i, putere)) % MOD;
        }
    return (ans / (n / 2 + 1)) % MOD;
}
void ciur(){
    int i, j;
    c[0] = c[1] = 1;
    for (i = 4; i <= NMAX; i += 2)
        c[i] = 1;
    for (i = 3; i <= RAD; i += 2)
        if (!c[i])
            for (j = i * i; j <= NMAX; j += 2 * i)
                c[j] = 1;
}
int main(){
    freopen("dirichlet.in", "r", stdin);
    freopen("dirichlet.out", "w", stdout);
    int n, i;
    scanf("%d", &n);
    ciur();
    printf("%d", catalan(2 * n, n));
    return 0;
}