#include<fstream>
#define mod 9999991
using namespace std;
ifstream f("dirichlet.in");
ofstream g("dirichlet.out");
long long n,i,fact,fac2,lol,in3,inv,sol,in2,put;
int main ()
{
	long long MO=mod;
	f>>n;
	fact=1;
	for(i=2;i<n;++i)
		fact=fact*i%mod;
	fac2=1;
	for(i=n+1;i<=2*n-1;++i)
		fac2=fac2*i%mod;
	put=mod-2;
	inv=1;
	while(put)
	{
		if(put&1)
			inv=inv*fact%mod;
		put>>=1;
		fact*=fact;
		fact%=mod;
	}
	in2=1;
	fact=2;
	put=mod-2;
	while(put)
	{
		if(put&1)
			in2=in2*fact%mod;
		put>>=1;
		fact*=fact;
		fact%=mod;
	}
	sol=(fac2*inv%mod+1)%mod*in2%mod;
	g<<sol;
	return 0;
}