#include<fstream>
using namespace std;

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

long long v[25], num, n, fact=1, k=1;

int main()
{
    f>>n;
    for (int i=2; i<=n; i++) fact=(fact*i)%9999991;
    v[0]=fact;
    for (int i=1; i<=23; i++) v[i]=(v[i-1]*v[i-1])%9999991;

    num=9999989;
    for (int i=23; i>=0; i--)
        if (num>=1<<i)
        {
            k=(k*v[i])%9999991; num-=1<<i;
        }
    fact=1;
    for (int i=n+2; i<=n<<1; i++) fact=(fact*i)%9999991;

    g<<(fact*k)%9999991;
    return 0;
}