#include <fstream>
#define ll long long

using namespace std;

ifstream fin("dirichlet.in");
ofstream fout("dirichlet.out");

const int MOD = 9999991;
int  N , sol[16] , nr , b , nf;

void back(int k)
{
	if(b==N)
	{
		for(int i=1;i<=N;++i)
			fout<<sol[i]<<"B ";
		fout<<'\n';
	}
	else
	if(k<=N)
	{
		for(int i=0;i<=k-b;++i)
			b+=sol[k] = i ,  back(k+1) , b-=i;
	}
}

void gcd(ll a,ll b,ll &x,ll &y)
{
	if(!b)
		y = 0 , x = 1;
	else
	{
		gcd(b,a%b,x,y);
		ll aux = x;
		x = y;
		y = aux - y*(a/b); 
	}
}

ll inv(int x)
{
	ll inv , ins;
	gcd(x,MOD,inv,ins);
	if(inv<=0) inv = MOD + inv%MOD;
	return inv;
}

int main()
{
	fin>>N;
	ll nf = 1, n1 , n2 , ans;
	for(int i=2;i<=N;++i)
		nf = (nf*i)%MOD;

	n2 = n1 = (nf *(N+1))%MOD;

	for(int i=N+2;i<=N*2;++i)
		n2 = ((ll)n2*i)%MOD;

	ans = (n2 *inv(nf))%MOD;
	ans = (ans*inv(n1))%MOD;

	fout<<ans<<'\n';
	return 0;
}