#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i,j,k) for(int i=j;i<=k;++i)
#define g(i,j,k) for(int i=j;i>=k;--i)
int n,m,s,l;
const int N=2e6;
int jc[N],ny[N],p,mo;
inline int ksm(int x,int p=mo-2,int y=1){for(;p;p/=2,x=x*x%mo)if(p&1)y=x*y%mo;return y;}
inline int C(int n,int m){return(n<m||m<0)?0:jc[n]*ny[m]%mo*ny[n-m]%mo;}
inline void ycl(int n){
	jc[0]=1;
	f(i,1,n)jc[i]=jc[i-1]*i%mo;
	ny[n]=ksm(jc[n]);
	g(i,n,1)ny[i-1]=ny[i]*i%mo;
}
int C(int a,int b,int c){return C(a,c)*C(b,c)%p;}
int D(int a,int b,int c){return(a||b||c)?D(a/p,b/p,c/p)*C(a%p,b%p,c%p)%p:1;}
int ask(int n,int m,int k){
	if(!k)return 0;
	int x=0,y=0,z=0,fx=m/p,fy=(m-p+1)/p;
	while(k%p)--k,z+=D(n,m-k,k);
	f(i,0,p-1)(fx==(m-i)/p?x:y)+=C(n%p,(m-i)%p,i%p);
	return(x%p*ask(n/p,fx,k/p)+y%p*ask(n/p,fy,k/p)+z)%p;
}
signed main(){
	cin>>n>>p;mo=p;ycl(p-1);
	cout<<(ksm(3,n)-ask(n,n,n/2+1)+p)*ksm(2)%p;
	return 0;
}