#include <fstream>
#define MOD 9999991
#define LL long long

using namespace std;

ifstream fin("dirichlet.in");
ofstream fout("dirichlet.out");

LL N;

void Modular_Reverse(LL &x, LL &y, LL A, LL B)
{
    if (B==0)
      x=1, y=0;
    else
    {
        Modular_Reverse(x, y, B, A % B);
        LL aux=x;
        x=y;
        y=aux-y*(A / B);
    }
}

LL Get_Catalan(LL N)
{
    LL i;
    LL ANS=1, fact=1;
    LL x, y;
    for (i=1; i<=N; i++)
    {
        fact*=i;
        fact%=MOD;
    }
    ANS=fact;
    for (i=N+2; i<=2*N; i++)
    {
        ANS*=i;
        ANS%=MOD;
    }
    x=y=0;
    Modular_Reverse(x, y, fact, MOD);
    if (x<0)
      x=MOD+(x % MOD);
    ANS*=x;
    ANS%=MOD;
    ANS*=x;
    ANS%=MOD;
    return ANS;
}

int main()
{
    fin >> N;
    fout << Get_Catalan(N) << '\n';
    fin.close();
    fout.close();
    return 0;
}