#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 FastPow(int a, int b) {
    long long a1=a, rez=1;
    for(; b; b>>=1) {
        if(b&1)
            rez=(rez*a1)%MOD;
        a1=(a1*a1)%MOD;
    }
    return rez;
}

inline int dirichlet(int p,int n) {
    int rez = 0;
    long long p1 = p;
    while(p1<=n) {
        rez+=n/p1;
        p1*=p;
    }
    return rez;
}

long long catalan(int n, int k) {
    putere[2] = dirichlet(2, n)-dirichlet(2, k)-dirichlet(2, n - k);
    for(int i=3; i<=n; i+=2)
        if(!c[i])
            putere[i] = dirichlet(i, n)-dirichlet(i, k)-dirichlet(i, n - k);
    int cop = n/2+1;
    while(cop % 2 == 0) {
        cop/=2;
        putere[2]--;
    }
    int d=3;
    while(d * d <= cop) {
        while(cop % d == 0) {
            cop/=d;
            putere[d]--;
        }
        d+=2;
    }
    if(cop>1)
        putere[cop]--;
    long long ans = 1;
    ans=(1LL * ans *(FastPow(2, putere[2]))) % MOD;
    for(int i=3; i<=n; i+=2)
        if(putere[i])
            ans =(1LL*ans*(FastPow(i, putere[i]))) % MOD;
    return ans;
}
void ciur(int n) {
    int lim;
    c[0]=c[1]=1;
    lim =(int)sqrt((double)n);
    for(int i=4; i<=n; i+=2)
        c[i]=1;
    for(int i=3; i<=lim; i+=2)
        if(!c[i])
            for(int 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\n", catalan(2 * n, n));
}