#include<cstdio>
#include<cmath>
const int MOD=9999991;
using namespace std;
bool c[2000005];
long long rez;
inline int fast_pow(int a,int b)
{
    long long a1=a,p;
    //if(b==0)
    //    return 0;
    for(p=1; b; b=b>>1)
    {
        if(b&1)
            p=(p*a1)%MOD;
        a1=(a1*a1)%MOD;
    }
    return p;
}
void ciur(int n)
{
    int i,j,lim;
    c[0]=c[1]=1;
    lim=(int)sqrt((double)n);
    for(i=4; i<=n; i=i+2)
        c[i]=1;
    for(i=3; i<=lim; i=i+2)
        if(c[i]==0)
            for(j=i*i; j<=n; j=j+2*i)
               c[j]=1;
}
inline int legendre(int k,int nr)
{
    long long p;
    int ans;
    ans=0;
    p=k;
    while(p<=1LL*nr)
    {
        ans=ans+1LL*nr/p;
        p=p*k;
    }
    return ans;
}
void catalan(int n)
{
    int i,x,num,a;
    x=2*n;
    num=1;
    rez=1;
    a=n+1;
    for(i=2; i<=x; i++)
      if(c[i]==0)
        {
            num=legendre(i,x)-2*legendre(i,n);
            a=n+1;
            while(a%i==0)
            {
                num--;
                a=a/i;
            }
            rez=(rez*fast_pow(i,num))%MOD;
        }
}
int main()
{
    freopen("dirichlet.in","r",stdin);
    freopen("dirichlet.out","w",stdout);
    int n;
    scanf("%d",&n);
    ciur(2*n);
    catalan(n);
    printf("%lld\n",rez);
    return 0;
}