#include<stdio.h>
#define modulo 9999991
long long c[1000005];
int main()
{
	freopen("dirichlet.in","r",stdin);
	freopen("dirichlet.out","w",stdout);
	long  n,i,j;
	scanf("%ld",&n);
	c[0]=1;
	c[1]=1;
	c[2]=2;
	c[3]=5;
	c[4]=14;
	for(i=5;i<=n;i++)
	{
		for(j=0;j<i;j++)
			c[i]=(c[i]+(long long)c[j]*c[i-j-1])%modulo;
	}	
	printf("%ld\n",c[n]);
	return 0;
}