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

int Catalan(int n)
{
	if(n==1)
		return 1;
	if(n==2)
		return 2;
	int i,j,lim,nr;
	n2=2*n;
	C[0][0]=C[0][2]=1;
	C[0][1]=2;
	for(i=3;i<=n2;i++)
	{
		C[1][0]=1;
		if(i<=n+1)
			C[1][i]=1;
		lim=min(i-1,n);
		for(j=1;j<=lim;j++)
			C[1][j]=(C[0][j-1]+C[0][j])%MOD;
		for(j=0;j<=n;j++)
			C[0][j]=C[1][j];
	}
	nr=C[1][n];
	nr=nr/(n+1);
	return nr;
}

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