#include<cstdio>
#define MOD 9999991
void read(),solve(),back(int,int);
long long C[1000010];
int i,n;
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("dirichlet.in","r",stdin);
	freopen("dirichlet.out","w",stdout);
	scanf("%d",&n);
}
void solve()
{
	C[1]=1;
	if(n==1)printf("1\n");
	for(i=1;i<n;i++)
	{
		C[i+1]=((4*i+2)*C[i])/(i+2);
		C[i+1]%=MOD;
	}
	printf("%lld\n",C[n]);
}