#include<bits/stdc++.h>
#define int long long
using namespace std;
int p,F[5000006],Inv[5000006];
int pw(int x,int y){
	int res=1;
	for(;y;y>>=1,x=x*x%p) if(y&1) res=res*x%p;
	return res;
}
int clc(int x,int y){
	if(x<y||y<0) return 0;
	return F[x]*Inv[y]%p*Inv[x-y]%p;
}
int C(int x,int y){
	if(y==0) return 1;
	return C(x/p,y/p)*clc(x%p,y%p)%p;
}
int slv(int n,int m){
	int res=0;
	for(int i=m/p*p;i<=m;i++) res=(res+C(i*2,i)*C(n,i*2))%p;
	if(m>=p){
		int t=slv(n/p,m/p-1);
		for(int i=0;i*2<p;i++) res=(res+t*C(i*2,i)*C(n%p,i*2))%p;
	}
	return res;
}
signed main(){
	int n;
	cin>>n>>p;
	for(int i=F[0]=1;i<p;i++) F[i]=F[i-1]*i%p;
	Inv[p-1]=p-1;
	for(int i=p-1;i;i--) Inv[i-1]=Inv[i]*i%p;
	cout<<((pw(3,n)-slv(n,n/2))*((-p)/2)%p+p)%p;
}