// by saubguiu a normal one.

#include <bits/stdc++.h>
using namespace std;

#define inline __inline__ __attribute__ ((always_inline))

#define int long long

namespace io {
    int pos;
    inline int read (int &p = pos){
        static int v; static char c;
        p = 0, v = 1, c = getchar ();
        while (! isdigit (c)){
            if (c == '-') v = - 1;
            c = getchar ();
        }
        while (isdigit (c)){
            p = (p << 1) + (p << 3) + (c - 48);
            c = getchar ();
        }
        return v == 1 ? p : - p;
    }
    inline void write (int x){
        static int sta[65], top; top = 0;
        if (x < 0) putchar ('-'), x = - x;
        do {
            sta[++ top] = x % 10; 
            x /= 10;
        } while (x);
        while (top) putchar (sta[top --] + 48);
    }
}

const int N = 1e6;
int n, mod, f[N + 5];
int inv[N + 5], inj[N + 5], jc[N + 5];

inline int C (int a, int b){ return jc[a] * inj[b] % mod * inj[a - b] % mod; }

inline int power (int a, int p){
    static int res; res = 1;
    while (p > 0){
        if (p & 1) res = res * a % mod;
        a = a * a % mod;
        p >>= 1;
    }
    return res;
}

signed main (){
    io::read (n), io::read (mod);
    inv[1] = inj[0] = inj[1] = jc[0] = jc[1] = 1;
    for (int i = 2;i < mod;++ i){
        inv[i] = inv[i - mod % i] * (mod / i + 1) % mod;
        inj[i] = inj[i - 1] * inv[i] % mod;
        jc[i] = jc[i - 1] * i % mod;
    }
    int ans = 1;
    for (int u = n, v, res;u;u /= mod){
        v = u % mod; res = 0;
        for (int i = 0;(i << 1) <= v;++ i)
            res = res + C (v, i << 1) * C (i << 1, i) % mod;
        ans = res % mod * ans % mod;
    }
    io::write ((power (3, n) - ans + mod) % mod * inv[2] % mod), putchar ('\n');

    return 0;
}