#include <bits/stdc++.h>
#define macro_expand(x) #x
#define print_macro(x) printf("%s\n",macro_expand(x))
#define FOR(i,l,r) for(LL i=(l),i##ADJK=(r);i<=i##ADJK;++i)
#define ROF(i,r,l) for(LL i=(r),i##ADJK=(l);i>=i##ADJK;--i)
using namespace std;
// TODO: your functions
typedef long long LL;
const LL MN=6005,RN=3000;
int c[MN][MN];
LL yans[MN],Mod,sub;
LL ad(LL x,LL y){return ((x+y)>=Mod)?(x+y-Mod):(x+y);}
LL dc(LL x,LL y){return ((x-y)<0)?(x-y+Mod):(x-y);}
LL ml(LL x,LL y){return (LL)x*y%Mod;}
LL add(LL &x,LL y){return ((x+=y)>=Mod)?(x-=Mod):x;}
LL dec(LL &x,LL y){return ((x-=y)<0)?(x+=Mod):x;}
LL ksm(LL x,LL y){
	LL ret=1;
	for(;y;y>>=1,x=ml(x,x))
		if(y&1)
			ret=ml(ret,x);
	return ret;
}
const int MP=1e6+5;
LL fac[MP],caf[MP];
LL binom(LL u,LL d){
	if(d<0||u<d)return 0;
	if(u<Mod)return ml(fac[u],ml(caf[d],caf[u-d]));
	return ml(binom(u/Mod,d/Mod),binom(u%Mod,d%Mod));
}
// 查询组合数前缀和？？
const LL mx=1e18+1;
map<__int128,LL> mp;
LL sum(LL n,LL u){
	auto tmp=mp.find(u*mx+n);
	if(tmp!=mp.end())return tmp->second;
	n=min(n,u);
	if(u<=Mod-1){
		LL ret=0;
		FOR(i,0,n)add(ret,binom(u,i));
		return ret;
	}
	int t=sum(n%Mod,u%Mod),ji=ksm(2,u%Mod);
	return mp[u*mx+n]=ad(ml(t,sum(n/Mod,u/Mod)),ml(dc(ji,t),sum(n/Mod-1,u/Mod)));
}
void init(int o, int p)
{
	// TODO: your init
	sub=o,Mod=p;
	if(sub<=2){
		c[0][0]=1;
		FOR(i,1,RN*2){
			c[i][0]=1;
			FOR(j,1,i)c[i][j]=ad(c[i-1][j-1],c[i-1][j]);
		}
		FOR(n,0,RN){
			FOR(j,0,n-1)add(yans[n],ml(c[2*n][j],n-j));
			yans[n]=ml(yans[n],2);
		}
	}else{
		fac[0]=1;
		FOR(i,1,Mod-1)fac[i]=ml(fac[i-1],i);
		caf[Mod-1]=ksm(fac[Mod-1],Mod-2);
		ROF(i,Mod-2,0)caf[i]=ml(caf[i+1],i+1);
		// cerr<<"Mod:"<<Mod<<endl;
	}
}
LL ask(LL n)
{
	if(sub<=2)return ml(yans[n],ksm((Mod+1)/2,2*n));
	else{
	// return sum(6,7);
		LL ret=0;
		FOR(i,0,Mod-1)if(n-1-i>=0)
			add(ret,ml(sum((n-1-i)/Mod,(2*n)/Mod),binom(2*n%Mod,i)));
		ret=ml(ret,n%Mod);
		FOR(i,0,Mod-1)if(n-1-i>=0)
			dec(ret,ml(sum((n-1-i)/Mod,2*n/Mod),ml(binom((2*n)%Mod,i),i)));
		return ml(ret,ksm((Mod+1)/2,2*n-1));
	}
}