#include <iostream>
#include <fstream>

using namespace std;

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

int p[100000],nrp, e[100000];
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;
    }
}

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++)
    {
        while(e[i]--)
        {
            sol=1ULL*sol*p[i]%MOD;
        }
    }

    g<<sol;

    return 0;
}