Ordinais ordinários

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

using i64 = long long;

i64 binpow(i64 b, i64 e, i64 MOD) {
  i64 res = 1;
  while (e > 0) {
    if (e & 1) res = (__int128_t)(res * b) % MOD;
    b = (__int128_t)(b * b) % MOD;
    e >>= 1;
  }
  return res;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);

  i64 n, m; cin >> n >> m;

  if (n == 0) {
    cout << 2 % m << '\n';
    return 0;
  }

  if (n == 1) {
    cout << 4 % m << '\n';
    return 0;
  }

  cout << (i64)((__int128_t)5LL * binpow(2, n + 1 - 2, m) % m - 1 + m) % m << '\n';
}

/*
  a(n) = 5*2^(n-2) - 1

  f[0] = 2;
  f[1] = 4;
  f[2] = f[0] + f[1] + (2-1) + 2 = 2 + 4 + 1 + 2 = 9;
  f[3] = f[0] + f[1] + f[2] + (3-1) + 2 = 2 + 4 + 9 + 2 + 2 = 19;
  f[4] = f[0] + f[1] + f[2] + f[3] + (4-1) + 2 = 34 + 5 = 39;
*/