#include <fstream>
#define MOD 9999991
#define ll long long
using namespace std;

ifstream fin ("dirichlet.in");
ofstream fout ("dirichlet.out");
ll n,i,nr1,nr2,x,y;
void invers_modular (ll a, ll b, ll &x, ll &y){
    if (b == 0)
        x = 1, y = 0;
    else {
        ll xa,ya;
        invers_modular (b,a%b,xa,ya);
        x = ya;
        y = xa - (a/b)*ya;
    }
}
int main (){

    fin>>n;
    nr1 = nr2 = 1;
    for (i=2;i<=2*n;i++)
        nr1 = (nr1*i) % MOD;

    for (i=1;i<=n;i++)
        nr2 = (((nr2*i) % MOD)*i) % MOD;
    nr2 = (nr2*(n+1)) % MOD;

    invers_modular (nr2,MOD,x,y);
    if (x < 0)
        x += MOD;

    fout<<x*nr1%MOD;

    return 0;
}