#include<cstdio>

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

int n, fr[N];

void pune(int x,int a[], int add) {
    for (int i = 2; i * i <= x; ++i)
        while (x % i == 0) {
            fr[i] += add;
            x /= 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 (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);

    scanf("%d", &n);

    formula();

    rez();

    return 0;
}