#include <stdio.h>

#define MAXN 1000010
#define MOD 9999991

int A[MAXN];
int i,j,N;
int sum;

inline int f(int N, int p)
{
	int sol = 0;
	while (N) {
		N /= p;
		sol += N;
	}
	return sol;
}

int main()
{
	freopen("dirichlet.in","r",stdin);
	freopen("dirichlet.out","w",stdout);
	
	scanf("%d\n",&N);
	for (i=1; 2*i+1<=2 * N; ++i){
		if (A[i] != 0) continue;
		for (j=3 * (2*i+1);  j <=2 * N; j+=2 * (2*i+1))
			A[(j-1)/2] = -1;
	}
	
	sum = 1LL;
	A[0] = f(2*N,2) - f(N,2) - f(N+1,2);
	for (j=1; j<=A[0]; ++j)
		sum = (1LL * sum * 2) % MOD;
	
	for (i=1; (2*i+1) <= 2 * N; ++i){
		if (A[i] != 0) continue;
		int prim = 2*i+1;
		A[i] = f(2*N, prim) - f(N, prim) - f(N+1, prim);
		for (j=1; j<=A[i]; ++j)
			sum = (1LL * sum * prim) % MOD;
	}
	
	printf("%d\n", sum);
	return 0;
}