#include <bits/stdc++.h>
using namespace std;
int op,mod,Phi;
long long jc[1000010],njc[1000010];
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 int 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; 
}
long long lucas(register int x,register int 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;
	jc[0]=1;
	for(int i=1;i<=p;++i)jc[i]=jc[i-1]*i%mod;
	njc[p]=qpow(jc[p],mod-2);
	for(int i=p-1;i>=0;--i)njc[i]=njc[i+1]*(i+1)%mod;
	return ;
}
int ask(long long n)
{
	long long ans=n%mod*lucas(2*n-1,n-1)%mod;
	ans*=qpow(qpow(2,2*n-1),mod-1);
	return ans%mod;
}