#include <iostream>
#include <fstream>

using namespace std;

ifstream f("dirichlet.in");
ofstream g("dirichlet.out");

int p[149000],nrp, e[149000];
bool v[2000002];

const int MOD=9999991;

void ciur(int n)
{
    int i,j;
    for( i=3;i*i<=n;i+=2)
    {
        if(v[i]==0)
            for( j=i*i;j<=n;j+=2*i)
                v[j]=1;
    }
    p[1]=2;
    nrp=1;
    for(i=3;i<=n;i+=2)
        if(v[i]==0)
            p[++nrp]=i;
}

int legendre(int n,int p)
{
    int exp=0;
    while(n>=p)
    {
        n/=p;
        exp+=n;
    }
    return exp;
}

void desc(int n, int p, int i)
{
    while(n%p==0)
    {
        e[i]--;
        n/=p;
    }
}


long long put2(int x, int n)
{
    long long val=1,a=x;
    while (n>0)
    {
        if(n%2!=0)
            val=val*a%MOD;
        a=a*a%MOD;
        n/=2;
    }
    return val;
}

int main()
{
    int n,sol=1;

    f>>n;
    ciur(2*n);


    for(int i=1;i<=nrp;i++)
    {
        e[i]=legendre(2*n,p[i])-legendre(n,p[i])-legendre(n+1,p[i]);
    }

    for(int i=1;i<=nrp;i++)
    {
       sol=sol*put2(p[i],e[i])%MOD;
    }

    g<<sol;

    return 0;
}