#include <bits/stdc++.h>
using namespace std;
const int mod=9999991;
int rid_put(int nr,int baza)
{
    long long bb=nr,rez=1;
    int cmp=baza;
    while(cmp)
    {
        if(cmp&1)
            rez*=bb,rez%=mod;
        bb*=bb;
        bb%=mod;
        cmp/=2;
    }
    return rez;
}
bool v[2000005];
void ciur()
{
     int i,j;
    v[0]=v[1]=1;
    for(i=4;i<=2000000;i+=2)v[i]=1;
    for(i=3;i*i<2000000;i+=2)
        if(!v[i])
        for(j=i*i;j<=2000000;j+=2*i)
        v[j]=1;
}
int main()
{
    freopen("dirichlet.in","r",stdin);
    freopen("dirichlet.out","w",stdout);
    int n;
    long long prod=1;
    scanf("%d",&n);
    int i;
    ciur();
    for(i=2;i<=2*n;i++)
    {
        if(v[i])continue;
        int cnt=0;
        int cp=2*n;
        while(cp)
        {
            cnt+=cp/i;
            cp/=i;
        }
        cp=n+1;
        while(cp)
        {
            cnt-=cp/i;
            cp/=i;
        }
        cp=n;
        while(cp)
        {
            cnt-=cp/i;
            cp/=i;
        }
        prod*=rid_put(i,cnt);
        prod%=mod;
    }
    printf("%lld",prod);
    return 0;
}