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