#include <cstdio>
#define MAX 1000000
#define mod 9999991
using namespace std;
char ciur[MAX+1];
void ciuruire()
{
    int i, prim=2;
    while(prim*prim<=MAX)
    {
        for(i=prim;i*prim<=MAX;i++)
            ciur[i*prim]=1;
        prim++;
        while(ciur[prim]==1)
            prim++;
    }
}
int putfact(int prim, long long n)
{
    int exp=0, p=prim;
    while(p<=n)
    {
        exp+=(n/p);
        p*=prim;
    }
    return exp;
}
long long ridicarelaput(long long f, long long exp)
{
    long long rez=1;
    while(exp)
    {
        if(exp%2==0)
        {
            f=(f*f)%mod;
            exp/=2;
        }
        else
        {
            rez=(rez*f)%mod;
            exp--;
        }
    }
    return rez;
}
int main()
{
    freopen("dirichlet.in", "r", stdin);
    freopen("dirichlet.out", "w", stdout);
    long long n, i, rasp=1, f1=1, f2=1, f3=1;
    scanf("%lld", &n);
    ciuruire();
    for(i=2;i<=2*n;i++)
    {
        if(ciur[i]==0)
        {
            f1=(f1*ridicarelaput(i, putfact(i, 2*n)))%mod;
            f2=(f2*ridicarelaput(i, putfact(i, n+1)))%mod;
            f3=(f3*ridicarelaput(i, putfact(i, n)))%mod;
        }
    }
    f2=ridicarelaput(f2, mod-2);
    f3=ridicarelaput(f3, mod-2);
    printf("%lld", (f1*f2*f3)%mod);
    return 0;
}