#include<stdio.h>

#define MaxN 1000100
#define Mod 9999991

int N,A[MaxN] = {0,1,1};

int main()
{
	FILE *f = fopen("dirichlet.in","r");
	FILE *g = fopen("dirichlet.out","w");
	
	fscanf(f,"%d ",&N);
	for(int i=3;i<=N+1;i++)
		for(int j=2;j<=i;j++)
		{
			A[j] += A[j-1];
			if(A[j] > Mod)
				A[j] -= Mod;
		}
	fprintf(g,"%d ",A[N]);
	
	fclose(g);
	fclose(f);
	return 0;
}