#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;
	C[2] = 2;
	C[3] = 5;
	
	for (int i = 4; i <= N; ++ i)
	{
		if (! (i % 2))
		{
			C[i] = (2 * C[i - 1]) % MOD;
			C[i] += 2 * C[i - 2];
			if (C[i] > MOD) C[i] %= MOD;
			
			for (int t = 2; t <= (i - 2) / 2; ++ t)
			{
				C[i] += 2 * C[t] * C[i - t - 1];
				if (C[i] > MOD) C[i] %= MOD;
			}
		}
		else
		{
			C[i] = (2 * C[i - 1]) % MOD;
			C[i] += 2 * C[i - 2];
			if (C[i] > MOD) C[i] %= MOD;
			
			for (int t = 2; t < i / 2 ; ++ t)
			{
				C[i] += 2 * C[t] * C[i - t - 1];
				if (C[i] > MOD) C[i] %= MOD;
			}
			
			C[i] += C[i / 2] * C[i / 2];
			if (C[i] > MOD) C[i] %= MOD; 
		}
		
	}
	
	
	printf ("%lld", C[N] % MOD);
	
	return 0;
}