/**********************************************************************************/
/*  Problem: d230 "IOI研習營模考2-1三元樹" from IOI                       */
/*  Language: CPP (644 Bytes)                                                     */
/*  Result: AC(0.4s, 288KB) judge by this@ZeroJudge                               */
/*  Author: lfs92002 at 2014-03-14 09:16:05                                       */
/**********************************************************************************/


#include<cstdio>
#include<algorithm>
using namespace std;
#define MOD 10000000
int base[15001];
inline int gcd(int a,int b)
{
	while((a%=b)&&(b%=a));
	return a+b;
}
int main()
{
	int n;
	int p,j;
	while(~scanf("%d",&n))
	{
		for(int i=2*n+1;i<=3*n;++i)
			base[i]=i;
		for(int i=1;i<=n;++i)
		{
			p=i,j=2*n+1;
			while(p!=1)
			{
				int d=gcd(p,base[j]);
				p/=d;
				base[j++]/=d;
			}
		}
		p=2*n+1;
		j=2*n+1;
		while(p!=1)
		{
			int d=gcd(p,base[j]);
			p/=d;
			base[j++]/=d;
		}
		long long ans=1;
		for(int i=2*n+1;i<=3*n;++i)
			ans=ans*base[i]%MOD;
		printf("%lld\n",ans);
	}
	return 0;
}