#include <iostream>
#include <cstdio>

using namespace std;

#define maxN 1000005
#define MOD 9999991

long long C[maxN];

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