Solution:

Part 1.当k是偶数时，则$$a_k = a_{k – 1} \times 2 = a_{k – 1} + 2 \times a_{k – 2} + 1$$。

Part 2.当k是奇数时，则$$a_k = a_{k – 1} \times 2 +1 = a_{k – 1} + 2 \times a_{k – 1} + 1$$。

#include <iostream>

using namespace std;

typedef long long LL;
LL MOD;
struct Matrix {
LL t[3][3];
Matrix operator * (const Matrix & m) const {
Matrix ret = {0};
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
ret.t[i][j] = (ret.t[i][j] + t[i][k] * m.t[k][j]) % MOD;
}
}
}
return ret;
}
};

const Matrix BASE = {{1, 2, 1, 1, 0, 0, 0, 0, 1}};

Matrix powMod(int pow, Matrix m) {
Matrix ret = {{1, 0, 0, 0, 1, 0, 0, 0, 1}};
while (pow) {
if (pow & 1) ret = ret * m;
m = m * m;
pow >>= 1;
}
return ret;
}

int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
LL n;
while (cin >> n >> MOD) {
if (n == 1) cout << 1 % MOD << "\n";
else if (n == 2) cout << 2 % MOD << "\n";
else {
Matrix trans = powMod(n - 2, BASE);
LL ans = (trans.t[0][0] * 2 + trans.t[0][1] * 1 + trans.t[0][2]) % MOD;
cout << ans << "\n";
}
}
return 0;
}