#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int maxn = 1000000 + 10;
i64 mod;
i64 fac[maxn], inv[maxn];
i64 qp(i64 a, i64 b)
{
    i64 c = 1;
    for (; b; b>>=1, a=a*a%mod)
        if (b & 1) c=c*a%mod;
    return c;
}
i64 C(int n, int m)
{
    if (n < m) return 0;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    i64 n;
    cin >> n >> mod;
    fac[0] = 1;
    for (int i=1;i<mod;++i) fac[i] = fac[i - 1] * i % mod;
    inv[mod - 1] = qp(fac[mod - 1], mod - 2);
    for (int i=mod-2;i>=0;--i) inv[i] = inv[i + 1] * (i + 1) % mod;
    i64 ans = 1;
    for (i64 x = n; x; x /= mod)
    {
        i64 s = 0;
        for (int i=0;i+i<=x%mod;++i) s = (s + C(x % mod, i) * C(x % mod - i, i)) % mod;
        ans = ans * s % mod;
    }
    cout << (qp(3, n) - ans + mod) % mod * (mod + 1ll) / 2 % mod << '\n';
    return 0;
}