#include<cstdio>
#include<cmath>
const int MOD=9999991;
using namespace std;
bool c[2000005];
int f[2000005];
long long num;
inline int fast_pow(int a,int b)
{
    long long a1=a,p;
    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[i]=1;
}
inline int legendre(int k,int nr)
{
    long long p;
    int rez;
    rez=0;
    p=k;
    while(p<=1LL*nr)
    {
        rez=rez+1LL*nr/p;
        p=p*k;
    }
    return rez;
}
void catalan(int n)
{
    int i,x;
    x=2*n;
    num=1;
    for(i=2; i<=x; i++)
      if(c[i]==0)
          f[i]=legendre(i,x);
    for(i=2; i<=n; i++)
        if(c[i]==0)
          f[i]=f[i]-2*legendre(i,n);
    for(i=2; i<=x; i++)
        num=(num*fast_pow(i,f[i]))%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",num/(n+1));
    return 0;
}