#include<bits/stdc++.h>
#define int long long
using namespace std;
int p,m,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 res=0;
	for(int i=0;i<=n/2;i++) res=(res+C(i*2,i)*C(n,i*2))%p;
	return res;
}
signed main(){
	cin>>m>>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,m)-slv(m))*((-p)/2)%p+p)%p;
}