#include <bits/stdc++.h>
using namespace std;
int op,mod,Phi;
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;
	if(y>x-y)y=x-y;
	long long a=1,b=1;
	for(register int i=0;i<y;++i)
	{
		(a*=(x-i))%=mod;
		(b*=(i+1))%=mod;
	}
	return a*qpow(b,mod-2)%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;
	Phi=p;
	for(int i=2;i*i<=p;++i)
	{
		if(p%i==0)
		{
			Phi/=i;
			Phi*=(i-1);
		}
	}
	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),Phi-1);
	return ans%mod;
}