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