#include <cstdio>
using namespace std;

const int MOD = 9999991;

long long GCD (long long A, long long B, long long &X, long long &Y) {
    if (!B) {
        X = 1; Y = 0;
        return A;
    } else {
        long long X1, Y1, D;

        D = GCD (B, A % B, X1, Y1);

        X = Y1;
        Y = X1 - (A/B) * 1LL * Y1;
        return D;
    }
}

inline long long getInverse (long long A) {
    long long X, Y, D;

    D = GCD (A, MOD, X, Y);

    if (X < 0)
        X = MOD + (X%MOD);

    return X;
}

inline long long getCombinations (long long N, long long K) {
    int X, Y;

    X = 1;
    for (int i = 2; i <= N; i ++)
        X = (X * 1LL * i) % MOD;

    Y = 1;
    for (int i = 2; i <= K; i ++)
        Y = (Y * i) % MOD;
    Y = getInverse (Y);

    return (((X * 1LL * Y) % MOD) * 1LL * Y) % MOD;
}

inline long long getCatalan (int N) {
    long long M = N;

    int X = getCombinations (2 * N, N);
    long long Y = getInverse (M + 1);

    return (X * 1LL * Y) % MOD;
}

int main () {

    freopen ("dirichlet.in" ,"r", stdin );
    freopen ("dirichlet.out","w", stdout);

    long long N;
    scanf ("%d", &N);

    if (N <= 1)
        printf ("1\n");
    else
        printf ("%lld\n", getCatalan(N));

    return 0;
}