#include<stdio.h>
#include<math.h>
#define MOD 9999991

bool p[2000041];
long long n;
void read () {
	scanf("%lld",&n);
}

void eratostene (bool e[],long long lim) {

	long long i,j;
	e[0]=1;
	e[1]=1;
	long long lim2=sqrt(lim)+1;
	for (i=4;i<=lim;i=i+2)
		e[i]=1;
	for ( i=3;i<=lim2;i=i+2)
		if (e[i]==0) {
			for ( j=i*i;j<=lim;j=j+(i<<1))
				e[j]=1;
		}
}

long multiplicitate (long &i , long &x) { 
	long suma=0,numitor=i;
	while (x/numitor) {
		suma=suma+x/numitor;
		numitor*=i;
	}
	return suma;
}

void rez() {
	long long e1,e2,e3,nr1,nr2,nr3,expo,asd;
	long long k=1,c,t;
	
	nr1=2*n;
	
	eratostene(p,nr1);

	nr2=n;
	nr3=n+1;
		
	for (long i=1;i<=nr1;i++) {
		if (p[i]==0) {
			e1=multiplicitate(i,nr1);
			e2=multiplicitate(i,nr2);
			e3=multiplicitate(i,nr3);
			expo=e1-e2-e3;
			t=(long long)i;
			c=1;
			for (;expo>0;expo>>=1) {
				if (expo&1) 
					c=(long long)c*t%MOD;
				t=(long long)t*t%MOD;
			}
			k=(long long)k*c%MOD;
		}
	}
	printf("%lld\n",k);
}

int main() {
	
	freopen("dirichlet.in","r",stdin);
	freopen("dirichlet.out","w",stdout);
	
	read();
	rez();
	return 0;
}