#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);
            	   ans=(1LL*ans*FastPow(i,p))%mod;
            }
    aux=n/2+1;
    d=2;
    while(d*d<=aux)
    {
        while(aux%d==0)
        {
            aux/=d;
						ans=(1LL*ans/d)%mod;
        }
        d++;
    }
    if(aux>1) ans=(1LL*ans/aux)%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;
}