#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int P,M,tot,pp[30],a[30],b[30],k[30],fac[1001000],phi[30],ks[30],ph,mm;
ll calcfacb(ll ip,int id){
	if(!ip)return 0;
	return calcfacb(ip/b[id],id)+ip/b[id];
}
int ksm(int x,ll y,int mod){
	int z=1;
	for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;
	return z;
}
int calcfacm(ll ip,int id){
	if(!ip)return 1;
	return 1ll*ksm(fac[pp[id]],ip/pp[id],pp[id])*fac[ip%pp[id]]%pp[id]*calcfacm(ip/b[id],id)%pp[id];
}
int C(ll x,ll y,int id){
	int A=calcfacm(x,id);
	A=1ll*A*ksm(calcfacm(y,id),phi[id]-1,pp[id])%pp[id]*ksm(calcfacm(x-y,id),phi[id]-1,pp[id])%pp[id];
	ll B=calcfacb(x,id)-calcfacb(y,id)-calcfacb(x-y,id);
	return 1ll*A*ksm(b[id],B,pp[id])%pp[id];
}
void newprime(int i){
	b[++tot]=i,pp[tot]=1;while(!(P%i))k[tot]++,P/=i,pp[tot]*=i;
	phi[tot]=pp[tot]/i*(i-1);
	fac[0]=1;for(int j=1;j<=pp[tot];j++)if(j%i)fac[j]=1ll*fac[j-1]*j%pp[tot];else fac[j]=fac[j-1];
}

void init(int o,int p)
{
	M=P=p;
	for(int i=2;i*i<=P;i++)if(!(P%i))newprime(i);
	if(P!=1)newprime(P);
	for(int i=1;i<=tot;i++)ks[i]=ksm(M/pp[i],phi[i]-1,pp[i]);
	ph=1;
	for(int i=1;i<=tot;i++)ph*=phi[i];
	mm=ksm(4,ph-1,M);
}
int ask(long long n)
{
	for(int i=1;i<=tot;i++)a[i]=C(2*n,n,i);
	int res=0;
	for(int i=1;i<=tot;i++)(res+=1ll*a[i]*ks[i]%M*(M/pp[i])%M)%=M;
	res=1ll*n%M*res%M;
    ll h=__gcd(n,1ll*ph);
    if(h==1)res=1ll*res*ksm(mm,n%ph,M)%M;
    else if(n>=ph)res=1ll*res*ksm(mm,n%ph+ph,M)%M;
    else res=1ll*res*ksm(mm,n,M)%M;
    return res;
}