#include <cstdio>
#include <cmath>
using namespace std;
const int MOD = 9999991;
const int NMAX = 1000000;
bool c[2 * NMAX + 5];
short int exponent[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 a1 = a, ans = 0;
    while (a1 <= b){
        ans += b / a1;
        a1 *= a;
    }
    return ans;
}
long long catalan(int n, int k){
    int i, d, aux;
    long long ans = 1;
    for (i = 2; i <= n; i ++)
        if (!c[i])
            exponent[i] = legendre(i, n) - legendre(i, k) - legendre(i, n - k);
    aux = n / 2 + 1;
    d = 2;
    while (d * d <= aux){
        while (aux % d == 0){
            aux /= d;
            exponent[d] --;
        }
        d ++;
    }
    if (aux > 1)
        exponent[aux] --;
    for (i = 2; i <= n; i ++)
        if (exponent[i] > 0)
            ans = (1LL * ans * (mypow(i, exponent[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, i;
    scanf ( "%d", &n );
    ciur ( 2 * n );
    printf( "%lld", catalan ( 2 * n, n ) );
    return 0;
}