#include <iostream>
#include <stdio.h>
#define i64 long long

using namespace std;

i64 mod = 9999991;

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


i64 put(i64 N, i64 P)
{
    i64 rez = 1;
    while(P)
    {
        if(P & 1)
            rez = (rez * N) % mod;
        N = (N * N) % mod;
        P >>= 1;
    }
    return rez;
}

int main()
{
    freopen ("diriclet.in","r",stdin);
    freopen ("diriclet.out","w",stdout);

    i64 N, i, val, C, P, A, X, Y;
    scanf("%lld", &N);
    for(i = 1, val = 1; i < N; i++)
    {
        C = 2 * ( 2 * i + 1);

        P = mod;
        A = i + 2;
        euclid(A, P, X, Y);
        while( X < 0 )
            X += N;

        val = ((val * C) % mod * X) % mod;
    }
    printf("%lld\n", val);
    return 0;
}