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