#include<stdio.h>

#define mod 9999991

FILE*f=fopen("dirichlet.in","r");
FILE*g=fopen("dirichlet.out","w");

int n,i,j,k;
int D[1005][1005];

int main () {
	
	fscanf(f,"%d",&n);
	D[1][0] = D[1][1] = 1;
	
	for ( i = 2 ; i <= n ; ++i ){
		for ( j = 0 ; j <= i ; ++j ){
			for ( k = j ; k >= j - i && k >= 0 ; --k ){
				D[i][j] += D[i-1][k];
				if ( D[i][j] >= mod )
					D[i][j] -= mod;
			}
		}
	}
	
	fprintf(g,"%d\n",D[n][n]);
	
	fclose(f);
	fclose(g);
	
	return 0;
}