#include <cstdio>
#include <algorithm>
using namespace std;

#define Mod 9999991
#define Nmax 2000002

FILE *f = fopen ( "dirichlet.in", "r" );
FILE *g = fopen ( "dirichlet.out", "w" );

int LgPow ( int A, int x ){

    int rez = 1;

    while ( x ){
        if ( x & 1 )
            rez = ( 1LL * rez * A ) % Mod;
        x >>= 1;
        A = ( 1LL * A * A ) % Mod;
    }

    return rez;
}

int Invers ( int N ){
    return LgPow( N, Mod-2 );
}

int main(){

    int N;

    fscanf ( f, "%d", &N );
    int F1 = 1, F2 = 1;
    int go = N+N;

    for ( int i = 1; i <= N; ++i )
        F1 = ( 1LL * F1 * i ) % Mod;
    for ( int i = N+1; i <= go; ++i )
        F2 = ( 1LL * F2 * i ) % Mod;

    int Sol = F2;
    int invN = Invers(F1);

    Sol = ( 1LL * Sol * invN ) % Mod;
    Sol = ( 1LL * Sol * Invers ( N+1 ) ) % Mod;

    fprintf ( g, "%d", Sol );

    return 0;
}