#include <stdio.h>
#define NMAX 2000004
#define MOD 9999991

int fact[NMAX];

void factorial(int n)
{
	int i;
	fact[0] = 1;
	for (i = 1; i <= 2 * n; ++i)
		fact[i] = (1ll * fact[i-1] * i) % MOD;
}

void euclid(long long a, long long b, long long *x, long long *y)
{
	if (b == 0) {
		*x = 1;
		*y = 0;
	}
	else {
		long long x0, y0;
		euclid(b, a % b, &x0, &y0);
		*x = y0;
		*y = x0 - (a / b) * y0;
	}
}

int main()
{
	freopen("dirichlet.in", "r", stdin);
	freopen("dirichlet.out", "w", stdout);
	int n;
	long long res = 1, x, y;
	scanf("%d", &n);
	n += 1;
	factorial(n);
	
	euclid(fact[n-1], MOD, &x, &y);	
	if (x < 0)
		x += MOD;
	res = (1ll * res * fact[2*n - 2]) % MOD;
	res = (1ll * res * x) % MOD;
	res = (1ll * res * x) % MOD;	
	euclid(n, MOD, &x, &y);
	if (x < 0)
		x += MOD;
	res = (1ll * res * x) % MOD;
	
	printf("%I64d\n", res);
	return 0;
}