#include <bits/stdc++.h>
using namespace std;
int op,mod,Phi;
long long jc[1000010],njc[1000010];
int CC[6010][6010];
inline long long qread()
{
	long long a=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){a=(a*10)+(ch^48);ch=getchar();}
	return a*f;
}
inline long long qpow(register long long x,register long long y)
{
	long long cx=1;
	while(y)
	{
		if(y&1)(cx*=x)%=mod;
		(x*=x)%=mod;
		y>>=1;
	}
	return cx;
}
inline long long C(register int x,register int y)
{
	if(x<y)return 0;
	return jc[x]*njc[y]%mod*njc[x-y]%mod; 
}
inline long long CCC(long long x,long long y)
{
	if(x-y<y)y=x-y;
	return CC[x+1][y];
}
long long lucas(register long long x,register long long y)
{
	if(y==0)return 1;
	return lucas(x/mod,y/mod)*C(x%mod,y%mod)%mod;
}
void init(int o, int p)
{
	op=o;mod=p;
	if(op==1||op==2)
	{
		for(int i=1;i<=6000;++i)
		{
			CC[i][0]=1;
			for(int j=1;j<=i;++j)
			{
				CC[i][j]=(CC[i-1][j]+CC[i-1][j-1])%mod;
			}
		}
		return ;
	}
	jc[0]=1;
	for(int i=1;i<p;++i)jc[i]=jc[i-1]*i%mod;
	njc[p-1]=qpow(jc[p-1],mod-2);
	for(int i=p-2;i>=0;--i)njc[i]=njc[i+1]*(i+1)%mod;
	return ;
}
int ask(long long n)
{
	long long ans;
	if(op==1||op==2)ans=n%mod*CCC(2*n-1,n-1)%mod;
	else ans=n%mod*lucas(2*n-1,n-1)%mod;
	ans*=qpow(qpow(2,2*n-1),mod-2);
	return ans%mod;
}