#include <fstream>
#define MOD 9999991

using namespace std;

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

int n;

int LogPow(int x, int pow){
    int aux = 1;
    while(pow){
        if(pow % 2){
            aux = (1LL * aux * x) % MOD;
            -- pow;
        }
        else{
            x = (1LL * x * x) % MOD;
            pow /= 2;
        }
    }
    return aux;
}

int main(int argc, const char * argv[]) {
    in>>n;
    
    int fact2n = 1, factn = 1, factn1 = 1;
    
    for(int i = 1; i <= n; ++ i)
        factn = (1LL * factn * i) % MOD;
    
    factn1 = (1LL * factn * (n + 1)) % MOD;
    fact2n = factn1;
    for(int i = n + 2; i <= 2 * n; ++ i)
        fact2n = (1LL * fact2n * (i)) % MOD;
    
    int power;
    
    power = MOD - 2;
    
    factn1 = LogPow(factn1, power);
    
    factn = LogPow(factn, power);
    
    out<<(1LL * ((1LL * fact2n * factn1) % MOD) * factn) % MOD;
    
    return 0;
}