#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 G(int a,int b,int c){return(a||b||c)?G(a/p,b/p,c/p)*C(a%p,b%p,c%p)%p:1;}
int F(int n,int m){
	if(!m)return 0;
	int x=0;
	if(m%p){
		x=F(n,m-1)+G(n,n-m+1,m-1);
	}else{
		f(i,0,p-1)x+=C(n%p,(n-i)%p,i);
		x=x%p*F(n/p,m/p);
	}
	return x%p;
}
signed main(){
	cin>>n>>p;mo=p;ycl(p-1);
	cout<<(ksm(3,n)-F(n,n+1)+p)*ksm(2)%p;
	return 0;
}