# include <cstdio>

const char *FIN = "dirichlet.in", *FOU = "dirichlet.out";
const int MAX = 1000005, MOD = 9999991;

int N, C[MAX];

inline int cat (int N) {
    C[0] = 1;
    for (int i = 1; i <= N; ++i) {
        int aux = 0;
        for (int j = 0; j < i; ++j)
            aux = (aux + 1LL * C[j] * C[i - 1 - j]) % MOD;
        C[i] = aux;
    }
    return C[N];
}

int main (void) {
    fscanf (fopen (FIN, "r"), "%d", &N);
    fprintf (fopen (FOU, "w"), "%d", cat (N));
}