#include<bits/stdc++.h>
using namespace std;
/*
 * Author: Yang
 * Date: 2024-12-03
 */
//#pragma GCC optimize(2)
using ll=long long;
using uint=unsigned int;
using ull=unsigned ll;
using pii=pair<int,int>;
#define all(v) begin(v),end(v)
#define fst first
#define scd second
#define rep(i,s,t) for(int i=(s);i<=(t);++i)
#define irep(i,t,s) for(int i=(t);i>=(s);--i)
template<typename T>
bool chmax(T &x,T y){return x<y?(x=y,1):0;}
template<typename T>
bool chmin(T &x,T y){return y<x?(x=y,1):0;}
const int Pmx=1e6+10;
int inv[Pmx];
int fac[Pmx],ifac[Pmx];
void work(){
    ll n,n0;int p;
    cin>>n>>p;
    n0=n;
    inv[1]=1;
    rep(i,2,p-1) inv[i]=1ll*(p-p/i)*inv[p%i]%p;
    fac[0]=ifac[0]=1;

    auto C=[&](int x,int y)->int {
        if(y<0||y>x) return 0;
        return 1ll*fac[x]*ifac[y]%p*ifac[x-y]%p;
    };
    auto qp=[&](int a,ll b){
        int r=1;
        while(b){
            if(b&1) r=1ll*r*a%p;
            a=1ll*a*a%p;b>>=1;
        }
        return r;
    };

    rep(i,1,p-1){
        fac[i]=1ll*fac[i-1]*i%p;
        ifac[i]=1ll*ifac[i-1]*inv[i]%p;
    }
    vector<int> dn;
    while(n){
        dn.push_back(n%p),n/=p;
    }
    int ans=1;
    for(int x:dn){
        int cur=0;
        rep(i,0,min(x/2,(p-1)/2)){
            // cout<<x<<": "<<i<<' '<<1ll*C(x,2*i)*C(2*i,i)%p<<"\n";
            (cur+=1ll*C(x,2*i)*C(2*i,i)%p)%=p;
        }
        // cout<<x<<' '<<cur<<'\n';
        ans=1ll*ans*cur%p;
    }
    // cout<<ans<<"\n";
    cout<<1ll*(qp(3,n0)+p-ans)*inv[2]%p<<"\n";
}
signed main(){
    //ios::sync_with_stdio(false);
    work();
}