#include <fstream>
using namespace std;

const int MOD = 9999991;

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

long long powmod(long long a, long long b) {
    long long r=1;
    while (b) {
        if(b&1) r=r*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return r;
}

int main()
{
    int N;
    f >> N;
    if(N==0){
        g << 1;
        return 0;
    }
    long long C = 1;
    for(int n=0;n<N;n++) {
        long long num =2LL*(2LL*n+1)%MOD;
        long long inv=powmod(n+2,MOD-2);
        C=C*num% MOD;
        C=C*inv%MOD;
    }

    g << C;
    return 0;
}