#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

const int MOD = 9999991;
long long  expo_r(int val,int putere){
    long long  raspuns = 1;
    while(putere>0){
        if(putere%2==1){
            raspuns = 1LL * raspuns * val % MOD;
        }
        val = 1LL * val*val  % MOD;
        putere/=2;
    }
    return raspuns;
}

long long  catalan(int n){
    long long c = 1;
    for(int i=1;i<=n;i++){
        c = 2LL * c * (2*i - 1) % MOD * expo_r(i+1, MOD-2) % MOD;
    }
    return c;
}

int main(){
    int n;
    fin>>n;
    fout<<catalan(n);

    return 0;
}