#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,jc[1000003],njc[1000003],MOD,v1[2],v2[2],ans;
int fstp(int X,int Y){int ret=1,bse=X%MOD;while(Y){if(Y%2)ret=ret*bse%MOD;bse=bse*bse%MOD;Y/=2;}return ret;}
int C(int X,int Y){
	if(X<Y||X<0||Y<0)return 0;
	return jc[X]*(njc[Y]*njc[X-Y]%MOD)%MOD;
}
void add(int &x,int y){x=(x+y)%MOD;return;}
signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>MOD;
	jc[0]=1;
	for(int i=1;i<MOD;i++)jc[i]=jc[i-1]*i%MOD;
	njc[MOD-1]=fstp(jc[MOD-1],MOD-2);
	for(int i=MOD-2;i>=0;i--)njc[i]=njc[i+1]*(i+1)%MOD;
	ans=fstp(3,n);
	v1[0]=1;
	while(n){
		int u=(n%MOD);
		v2[0]=v1[0];v2[1]=v1[1];
		v1[0]=v1[1]=0;
		for(int i=0;i<MOD;i++){
			add(v1[(i*2>=MOD)],v2[0]*(C(u,(i*2%MOD))*C((i*2%MOD),i)%MOD));
			add(v1[((i*2+1)>=MOD)],v2[1]*(C(u,((i*2+1)%MOD))*C(((i*2+1)%MOD),i)%MOD));
		}
		n/=MOD;
	}
	ans=(ans-v1[0])%MOD;
	ans=ans*((MOD+1)/2)%MOD;
	ans%=MOD;
	ans+=MOD;
	ans%=MOD;
	cout<<ans;
	return 0;
}