#include <cstdio>

#define modulo 9999991

int N;

int invers(int A, int p)
{
    long long aux;

    if (p == 1) return A;
    aux = invers(A, p>>1);
    if (p&1) return (((aux*aux) % modulo) *A) % modulo;
       else return (aux*aux) % modulo;
}

int catalan(int N)
{
    int i = 1;
    long long C = 1;
    
    if (N>750000) { i=750000; C=4979452; }
    else if (N>500000) { i=500000; C=6089115; }
    else if (N>250000) { i=250000; C=7307011; }
    for (; i<N; ++i)
    {
        C = (C* 2*(2*i+1)) % modulo;
        C = (C * invers(i+2, modulo-2)) % modulo;
    }

    return C;
}

int main()
{
    freopen("dirichlet.in","r",stdin);
    freopen("dirichlet.out","w",stdout);
    
    scanf("%d", &N);
    printf("%d\n", catalan(N));        
        
    return 0;
}