#include <iostream>
#include <fstream>

using namespace std;
const long long mod=9999991;
long long ans,fact,ind,X[40],Y[40];
int n;
void gcde(long long A,long long B,int lev)
{
    if(B==0)
    {
        X[lev]=1;
        Y[lev]=0;
        return;
    }
    gcde(B,A%B,lev+1);
    X[lev]=1LL*Y[lev+1];
    Y[lev]=1LL*(X[lev+1]-(A/B)*Y[lev+1]);
}
long long inv(long long A)
{
    gcde(A,mod,1);
    return ((X[1]%mod)+mod*(X[1]<0));
}
long long factorial(long long N)
{
    while(ind<=N)
    {
        fact*=ind;
        fact%=mod;
        ind++;
    }
    return fact;
}
int main()
{
    ifstream f("dirichlet.in");
    ofstream g("dirichlet.out");
    f>>n;
    ans=inv(n+1);
    ind=fact=1;
    ans*=inv(factorial(n));
    ans%=mod;
    ans*=inv(factorial(n));
    ans%=mod;
    ans*=factorial(2*n);
    ans%=mod;
    g<<ans;
    return 0;
}