#include <stdio.h>
#include <stdlib.h>
#define MOD 9999991


long long invMod(long long a, long long m) {
    long long x, y;

    euclid(a, m, &x, &y);

    if (x < 0)
        x += ((-x) / m + 1) * m;

    return x;
}

void euclid(long long a, long long m, long long *x, long long *y) {
    if(m == 0) {
        *x = 1;
        *y = 0;
    }
    else {
        long long x0, y0;
        euclid(m, a % m, &x0, &y0);
        *x = y0;
        *y = x0 - (a / m) * y0;
    }
}

int main() {
    long long prod, rasp, n_fact;
    int n, i;
    FILE *fin, *fout;

    fin = fopen("dirichlet.in", "r");
    fscanf(fin, "%d", &n);
    fclose(fin);

    prod = 1;
    n_fact = n + 1;
    for(i = 1; i <= n; i++) {
        prod = prod * (n + i) % MOD;
        n_fact = n_fact * i % MOD;
    }

    rasp = ((prod % MOD) * (invMod(n_fact, MOD) % MOD)) % MOD;

    fout = fopen("dirichlet.out", "w");
    fprintf(fout, "%lld", rasp);
    fclose(fout);
    return 0;
}