#include<fstream>
#define MOD 9999991
using namespace std;
ifstream fin("dirichlet.in");
ofstream fout("dirichlet.out");
int n;
long long sol, fact1, fact2;
void euclid( long long a, long long b, long long &x, long long &y ){
    if( b == 0 ){
        x = 1;
        y = 0;
    }else{
        long long x1 = 0, y1 = 0;
        euclid( b, a % b, x1, y1 );
        x = y1;
        y = x1 - a / b * y1;
    }
    return ;
}
long long InversMod( long long x ){
    long long invsmod = 0;
    long long k = 0;
    euclid( x, MOD, invsmod, k );
    if( invsmod <= MOD ){
        invsmod += MOD;
    }
    return invsmod;
}
int main(){
    fin >> n;
    fact1 = 1;
    for( int i = 2; i <= n; i++ ){
        fact1 = fact1 * 1LL * i;
        fact1 %= MOD;
    }
    fact2 = fact1;
    for( int i = 1; i <= n; i++ ){
        fact2 = fact2 * 1LL * ( i + n );
        fact2 %= MOD;
    }
    sol = ( 1LL * InversMod( n + 1 ) ) % MOD;
    sol = ( 1LL * sol * fact2 ) % MOD;
    sol = ( 1LL * sol * InversMod(fact1) ) % MOD;
    sol = ( 1LL * sol * InversMod(fact1) ) % MOD;
    fout << sol;
    return 0;
}