#include <iostream>
#include <cstdio>

using namespace std;

#define maxN 1005
#define MOD 9999991

int dp[maxN][maxN];

int main()
{
	freopen ("dirichlet.in", "r", stdin);
	freopen ("dirichlet.out", "w", stdout);
	
	int N;
	
	scanf ("%d", &N);
	
	for (int i = 0; i <= N; ++ i) dp[0][i] = 1, dp[i][0] = 1;
	dp[1][1] = 1;
	
	for (int i = 1; i <= N; ++ i)
		for (int j = 2; j <= N; ++ j)
		{
			dp[i][j] = 0;
			
			if (i > j) continue;
			for (int t = 0; t <= j; ++ t) dp[i][j] += dp[t][j - 1];
			
			dp[i][j] %= MOD;
		}
	
	printf ("%d", dp[N][N] - dp[N][N - 1]);
	
	return 0;
}