#include<cstdio>

const int MOD = 9999991;
const int N = 2000002;
const int M = 300000;

int n, fr[N], p[M], nr;
bool c[N];

void ciur() {
    for (int i = 2; i * i < N; ++i)
        if (!c[i])
            for (int j = i * i; j < N; j += i)
                c[j] = true;

    for (int i = 2; i < N; ++i)
        if (!c[i])
            p[++nr] = i;
}

void pune(int x, int a[], int add) {
    for (int i = 1; i <= nr && p[i] * p[i] <= x; ++i)
        while (x % p[i] == 0) {
            fr[p[i]] += add;
            x /= p[i];
        }

    if (x != 1)
        fr[x] += add;
}

void formula() {
    for (int i = n + 2; i <= 2 * n; ++i)
        pune(i, fr, 1);

    for (int i = 2; i <= n; ++i)
        pune(i, fr, -1);
}

void rez() {
    long long r = 1;
    for (int i = 2; i < N; ++i)
        for (short int j = 1; j <= fr[i]; ++j)
            r = (long long) r * i % MOD;

    printf("%lld\n", r);
}

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

    ciur();

    scanf("%d", &n);

    formula();

    rez();

    return 0;
}