#include <stdio.h>
#define MOD 9999991
#define NMAX 1005
int n,A[NMAX][NMAX],rez;
int main()
{
	freopen("dirichlet.in","r",stdin);
	freopen("dirichlet.out","w",stdout);
	scanf("%d",&n);
	int i,j;
	A[1][0]=1; A[1][1]=2; A[1][2]=2;
	for (i=2; i<=n; i++)
	{
		A[i][0]=1;
		for (j=1; j<=i; j++)
		{
			if (j-i>0)
				A[i][j]=A[i-1][j]-A[i-1][j-i-1];
			else
				A[i][j]=A[i-1][j];
			if (A[i][j]<0)
				A[i][j]+=MOD;
			A[i][j]+=A[i][j-1];
			if (A[i][j]>=MOD)
				A[i][j]-=MOD;
		}
		A[i][i+1]=A[i][i];
	}
	rez=A[n][n]-A[n][n-1];
	if (rez<0)
		rez+=MOD;
	printf("%d\n",rez);
	return 0;
}