#include <algorithm>
#include <iostream>
#include <cstring>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#define int long long

using namespace std;


const int N = 2e5+10;
int T, n, m;
/*
过程
Sn = 1*a1 + 1*a2 + ... + 1*a3;
Tn = 1*a1 + 2*a2 + ... + n*an;

设 Pn = n*Sn - Tn

2. Pn+1 = (n+1)Sn+1 - Tn+1  = ((n+1) -1)a1 + ((n+1) -2)a2 + ... + ((n+1) - (n-1) )an-1 + ((n+1) - n)an;
1. Pn   =    n*Sn   - Tn    = ( n    -1)a1 + ( n    -2)a2 + ... + ( n    - (n-1) )an-1 + ( n    - n)an; 

2. - 1. = Pn+1 - Pn         =           a1 +           a2 + ... +                 an-1 +            an;

3.Pn = n*Sn - Tn --> Tn = n*Sn - Pn
4.Pn+1 - Pn = Sn --> Pn = Pn-1 + Sn-1
5.Sn = Sn-1 + an;
6.an = an-1 + an-2

3.4.5.6. -> a[4][4]
*/
int ans[4] = {1, 1, 1, 0}; //a1, a2, S1, p1 
int a[4][4] = {
    {0,1,0,0},
    {1,1,1,0},
    {0,0,1,1},
    {0,0,0,1}
};

void c1()
{
    int temp[4] = {0};
    for(int i = 0; i<4; i++)
    {
        for(int j = 0; j<4; j++)
        {
            temp[i] += (ans[j] * a[j][i]) % m;
        }
    }
//  cout << temp[0] << " " << temp[1] << " " << temp[2] << " " << temp[3] << "\n";
    memcpy(ans, temp, sizeof ans);
}
void c2()
{
    int temp[4][4] = {0};
    for(int i = 0; i<4; i++)
    {
        for(int j = 0; j<4; j++)
        {
            for(int k = 0; k<4; k++)
            {
                temp[i][j] += (a[i][k]*a[k][j]) % m;
            }
        }
    }
    memcpy(a, temp, sizeof a);
}

void qsm(int x)
{
    while(x)
    {
        if(x & 1)
        {
            c1();
        }
        c2();
        x >>= 1;
    }
}

void solve()
{
    cin >> n >> m;
    qsm(n-1);
//  cout << ans[0] << " " << ans[1] << " " << ans[2] << " " << ans[3] << "\n";
    cout << (n * ans[2] - ans[3]) % m << "\n";
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    T = 1;
//    cin >> T;
    while(T--)
    {
        solve();
    }
    return 0;
}