#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
long v[1000001];
long n;
long long s=1;
void back(int k,int r) 
{
	int i;
	if(k==n+1) 
	{
		if(r==0)
			s++;
	}
	else 
		for(i=0;i<=r;i++) 
		{
			v[k]=i;
			if(n-(r-i)<=i)
				back(k+1,r-i);
		}
}
int gcd(int a,int b) 
{
	int x=0,y=1,lx=1,ly=0;
	int aux,aux2;
	while(b) 
	{
		aux=a/b;
		aux2=b;
		b=a%b;
		a=aux2;
		aux2=x;
		x=lx-aux*x;
		lx=aux2;
		aux=y;
		y=ly-aux*y;
		ly=aux2;
	}
	return lx;
}
int main() 
{
	freopen("dirichlet.in","r",stdin);
	freopen("dirichlet.out","w",stdout);
	int i;
	long long prod=1,inv,aux;
	scanf("%ld",&n);
	s=1;
	for(i=1;i<=n;i++) 
	{
		aux=s;
		s=((long long)(i+i+i+i-2)*aux)%9999991;
	}
	for(i=2;i<=n+1;i++) 
		prod=((long long)prod*i) %9999991;
	inv=gcd(prod,9999991);
	if(inv<=0) 
		inv=9999991+inv%9999991;
	s=((long long)s*inv)%9999991;
	printf("%lld\n",s);
	return 0;
}