#include <cstdio>
using namespace std;
const int MOD = 9999991;
int main(){
    freopen("dirichlet.in", "r", stdin);
    freopen("dirichlet.out", "w", stdout);
    int n, i;
    long long cat;
    scanf("%d", &n);
    cat = 1;
    for (i = 1; i < n; i ++)
        cat = (cat * 2 * (2 * n + 1) / (n + 2)) % MOD;
    printf("%lld", cat);
    return 0;
}