#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>900000) { i=900000; C=8997602; }
    else if (N>850000) { i=850000; C=3920856; }
    else if (N>750000) { i=750000; C=4979452; }
    else if (N>600000) { i=600000; C=1337563; }
    else if (N>500000) { i=500000; C=6089115; }
    else if (N>450000) { i=450000; C=3693784; }
    else if (N>350000) { i=350000; C=3326446; }
    else if (N>250000) { i=250000; C=7307011; }
    else if (N>200000) { i=200000; C=3281720; }
    else if (N>100000) { i=100000; C=1812692; }
    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;
}