#include<fstream>
#include<cstring>
#define MOD 9999991
using namespace std;
int n,sol,C[2][800010],aux[800010];

void Produs(int A[], int B)
{
	int i, t = 0;
    for (i = 1; i <= A[0] || t; i++, t /= 10)
        A[i] = (t += A[i] * B) % 10;
    A[0] = i - 1;
}

void Impartire(int A[], int B)
{
	int i, t = 0;
    for (i = A[0]; i > 0; i--, t %= B)
        A[i] = (t = t * 10 + A[i]) / B;
    for (; A[0] > 1 && !A[A[0]]; A[0]--);
}

int Rest(int A[], int B)
{
	int i, t = 0;
    for (i = A[0]; i > 0; i--)
        t = (t * 10 + A[i]) % B;
    return t;
}

int Catalan()
{
	if(n<2)
		return 1;
	if(n==2)
		return 2;
	int i;
	C[0][0]=1; C[0][1]=2;
	for(i=3;i<=n;i++)
	{
		memcpy(C[1],C[0],sizeof(C[0]));
		Produs(C[1],4*i-2);
		Impartire(C[1],i+1);
		memcpy(C[0],C[1],sizeof(C[1]));
	}
	return Rest(C[1],MOD);
}

int main()
{
	ifstream fin("dirichlet.in");
	fin>>n;
	fin.close();
	sol=Catalan();
	ofstream fout("dirichlet.out");
	fout<<sol<<"\n";
	fout.close();
	return 0;
}