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