#include <fstream>
#define ll long long
#define mod 9999991

using namespace std;

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

ll x, y, xx, yy, n, rez=1;

ll factorial(ll x)
{
    ll rez=1;
    for (ll i=2; i<=x; ++i)
        rez*=i, rez%=mod;
    return rez;
}

ll euclid(ll a, ll b, ll &x, ll &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    else
    {
        ll x0,y0,d;
        d=euclid(b,a%b,x0,y0);
        x=y0;
        y=x0-(a/b)*y0;
        return d;
    }
}

int main()
{
    f>>n;
    rez*=factorial(2*n);
    rez%=mod;
    euclid(factorial(n+1),mod,x,y);
    while (x<0) x+=mod;
    euclid(factorial(n),mod,xx,y);
    while (xx<0) xx+=mod;
    rez*=x;
    rez%=mod;
    rez*=xx;
    rez%=mod;
    g<<rez;
    return 0;
}