#include <cstdio>
#include <cmath>
using namespace std;
const int mod=9999991;
bool c[2000005];
void ciur(int n) {
    int lim,i,j;
    c[0]=c[1]=1;
    lim =(int)sqrt((double)n);
    for(i=4; i<=n; i+=2)
        c[i]=1;
    for(i=3; i<=lim; i+=2)
        if(!c[i])
            for(j=i*i; j<=n; j+=2*i)
                c[j]=1;
}
long long FastPow(int a,int b) {
    long long a1=a,p=1;
    for(p=1; b; b>>=1) {
        if(b&1)
            p=(p*a1)%mod;
        a1=(a1*a1)%mod;
    }
    return p;
}
int legendre(int a, int n) {
    long long a1=a;
    int ans=0;
    while(a1<=n) {
        ans=ans+n/a1;
        a1*=a;
    }
    return ans;
}
long long catalan(int n,int k) {
    int i,d,aux,p;
    long long ans=1;
    for (i=2; i<=n; i++)
        if(!c[i]) 
					{
            p=legendre(i,n)-legendre(i,k)-legendre(i,n-k);
            aux=n/2+1;
            while(aux%i==0) 
            {
                p--;
				        aux/=i;
            }
            ans=(1LL*ans*FastPow(i,p))%mod;
        }
    return ans;
}
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));
    return 0;
}