#include <bits/stdc++.h>
using namespace std;const int mod=9999991;int rid_put(int nr,int baza){long long bb=nr,rez=1;int cmp=baza;while(cmp){if(cmp&1)rez*=bb,rez%=mod;bb*=bb;bb%=mod;cmp/=2;}return rez;}bool v[2000005];void ciur(){int i,j;v[0]=v[1]=1;for(i=4;i<=2000000;i+=2)v[i]=1;for(i=3;i*i<2000000;i+=2)if(!v[i])for(j=i*i;j<=2000000;j+=2*i)v[j]=1;}int main(){freopen("dirichlet.in","r",stdin);freopen("dirichlet.out","w",stdout);int n;long long prod=1;scanf("%d",&n);int i;ciur();for(i=2;i<=2*n;i++){if(v[i])continue;int cnt=0;int cp=2*n;while(cp){cnt+=cp/i;cp/=i;}cp=n+1;while(cp){cnt-=cp/i;cp/=i;}cp=n;while(cp){cnt-=cp/i;cp/=i;}prod*=rid_put(i,cnt);prod%=mod;}printf("%lld",prod);return 0;}