#include <fstream.h>
#include<iostream.h>

#define MOD 9999991
#define mx 1111111111

using namespace std;

int invers (int x, int p )
{
    if (p==1)
     return x;
     else
     {
         long long val;
                    val=invers (x,p/2);
                    val=(val*val);
                    if (p%2) val*=x;
                    val%=MOD;
                    return val;
                    }
    }

int main()
{
    long long p1,p2,i;
    int n;
    ifstream f("dirichlet.in");
    ofstream g("dirichlet.out");
    f>>n;
  
    p1=1;p2=1;
    for (i=2;i<=n;++i)
    {
        p1*=i;p2*=(i+n);
        if (p1>mx ) p1%=MOD;
        if (p2>mx ) p2%=MOD;
        }
        g<<mx;
    p1%=MOD;p2%=MOD;
    p1=invers (p1,MOD-2);
    g<<p1*p2%MOD;
   
    g.close();
    f.close();
    return 0;
}