#include <stdio.h>
#define MAXN 1000010
#define M 9999991
long long a0[MAXN], a1[MAXN];
long n, i, j;
int main()
{
	freopen("dirichlet.in","r",stdin);
	freopen("dirichlet.out","w",stdout);
	scanf("%ld", &n);
	for (i=1;i<=n; i++)
	{
		a1[1]=i;
		for (j=2; j<=i; j++)
			a1[j]=(a0[j]+a1[j-1])%M;
		for (j=1; j<=i; j++)
			a0[j]=a1[j];
	}//for i
	printf("%lld\n", a1[n-1]);
	return 0;
}//main