#include<cstdio>
#define MOD 9999991;
long long c[1000011],ex[2000011],i,n,j,p;
using namespace std;
int exp(int pr,int n)
{
    long long put,sum;
    put=pr;
    sum=0;
    while (n/put>0)
    {
        sum=sum+n/put;
        put*=pr;
    }
    return sum;
}
int pow(int f,int p)
{
    if (p==0) return 1;
    long long aux=1;
    while (p>0)
    {
        if (p%2==0)
        {
            f=(f*f)%MOD;
            p=p/2;
        }
        else {
                p--;
                aux=(aux*f)%MOD;
             }
    }
    return aux%MOD;
}

int main()
{
    freopen("dirichlet.in","r",stdin);
    freopen("dirichlet.out","w",stdout);
    int nr=0;
    scanf("%d",&n);
    for(i=2;i<2*n;i++)
    {
        bool ok;
        ok=true;
        for(j=1;j<=nr&&c[j]*c[j]<=i;j++)
            if (i%c[j]==0)
                ok=false;
        if (ok)
        {
            nr++;
            c[nr]=i;
        }
    }
    for(i=1;i<=nr;i++)
    {
        ex[c[i]]=(exp(c[i],2*n)-exp(c[i],n)-exp(c[i],n+1))%MOD;
    }
    p=1;
    for(i=1;i<=nr;i++)
    {
        if (ex[c[i]]!=0)
        p=(p*pow(c[i],ex[c[i]]))%MOD;
    }
    printf("%d\n",p);
}