// vvvvvvvvvvvv TEMPLATE vvvvvvvvvvvv
#include <bits/stdc++.h>
using namespace std; using ll = long long; using P = pair<ll, ll>;
const ll linf = 1e18; const double eps = 1e-12, pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define each(i,a) for (auto&& i : a)
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)
#define min(x,y) (x < y ? x : y)
#define max(x,y) (x < y ? y : x)
template<typename Head> void out(Head h) { cout << h << endl; } template<typename Head, typename... Tail>void out(Head h, Tail... t) { cout << h << " "; out(t...); }
template<typename T> istream& operator>>(istream& is, vector<T>& v) { each(x,v) is >> x; return is; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) { rep(i,v.size()) { if (i) os << " "; os << v[i]; } return os; }
template<typename T> ostream& operator<<(ostream& os, const vector<string>& v) { rep(i,v.size()) { if (i) os << endl; os << v[i]; } return os; }
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) { rep(i,v.size()) { if (i) os << endl; os << v[i]; } return os; }
struct yes_no : std::numpunct<char> { string_type do_truename() const { return "Yes"; } string_type do_falsename() const { return "No"; } };
void solve(); int main() {
  ios::sync_with_stdio(false); cin.tie(0); locale loc(locale(), new yes_no); cout.imbue(loc); cout << fixed << setprecision(10) << boolalpha;
  solve();
}
// ^^^^^^^^^^^^ TEMPLATE ^^^^^^^^^^^^

ll mod = 1e9+7;
ll mul(ll a, ll b) { return a * b % mod; }
ll mul(initializer_list<ll> t) { ll res = 1; each(v, t) res = mul(res, v); return res; }
ll add(ll a, ll b) { return (a + b) % mod; }
ll add(initializer_list<ll> t) { ll res = 0; each(v, t) res = add(res, v); return res; }
ll sub(ll a, ll b) { return (a - b + mod) % mod; }
ll sub(initializer_list<ll> t) { auto it = t.begin(); ll res = *(it++); while (it != t.end()) res = sub(res, *(it++)); return res; }
ll inv(ll n); ll power(ll x, ll n) { if (n < 0) return inv(power(x, -n)); ll res = 1; for (ll i = 1; i <= n; i <<= 1) { if (i & n) res = mul(res, x); x = mul(x, x); } return res; }
ll inv(ll n) { return power(n, mod-2); }
ll divi(ll a, ll b) { return mul(a, inv(b)); }
ll divi(initializer_list<ll> t) { auto it = t.begin(); ll res = *(it++); while (it != t.end()) res = divi(res, *(it++)); return res; }
// template<size_t n> struct Fact { ll fact[n+1]; public: constexpr Fact() : fact() { fact[0] = 1; rep(i, 1, n+1) fact[i] = fact[i-1] * i % mod; } ll operator[](size_t idx) const { return fact[idx]; } };
// constexpr auto fact = Fact<size_t(300000)>();
// ll comb(ll n, ll r) { if (r < 0) return 0; if (r > n) return 0; return divi(fact[n], mul(fact[r], fact[n-r])); }

using Row = vector<ll>;
using Matrix = vector<Row>;
Matrix E(ll n) { Matrix res(n, Row(n, 0)); rep(i, n) res[i][i] = 1; return res; }
Matrix mul(const Matrix& A, const Matrix& B) { const ll n = A.size(), m = A[0].size(), l = B[0].size(); assert(m == B.size()); Matrix res(n, Row(l, 0)); rep(i, n) rep(j, m) rep(k, l) res[i][k] = add(res[i][k], mul(A[i][j], B[j][k])); return res; }
Row mul(const Matrix& A, const Row& x) { Matrix tx(x.size()); rep(i, x.size()) tx[i] = Row(1, x[i]); tx = mul(A, tx); Row res(x.size()); rep(i, x.size()) res[i] = tx[i][0]; return res; }
Matrix power(Matrix A, ll n) { assert(A.size() == A[0].size()); Matrix res = E(A.size()); for (ll i = 1; i <= n; i <<= 1) { if (i & n) res = mul(res, A); A = mul(A, A); } return res; }

using Graph = array<array<ll, 4>, 4>;

void output_graph(const Graph& g) {
  cout << "┌┐";
  if (g[0][1]) {
    cout << "─→";
  }
  else {
    cout << "    ";
  }
  cout << "┌┐" << endl;

  cout << "└┘";
  if (g[1][0]) {
    cout << "←─";
  }
  else {
    cout << "    ";
  }
  cout << "└┘" << endl;

  if (g[0][2]) cout << "│";
  else cout << "  ";
  if (g[2][0]) cout << "↑";
  else cout << "  ";

  if (g[0][3]) cout << "↘";
  else cout << "  ";
  if (g[1][2]) cout << "↙";
  else cout << "  ";

  if (g[1][3]) cout << "│";
  else cout << "  ";
  if (g[3][1]) cout << "↑";
  else cout << "  ";
  cout << endl;

  if (g[0][2]) cout << "↓";
  else cout << "  ";
  if (g[2][0]) cout << "│";
  else cout << "  ";

  if (g[2][1]) cout << "↗";
  else cout << "  ";
  if (g[3][0]) cout << "↖";
  else cout << "  ";

  if (g[1][3]) cout << "↓";
  else cout << "  ";
  if (g[3][1]) cout << "│";
  else cout << "  ";
  cout << endl;

  cout << "┌┐";
  if (g[2][3]) {
    cout << "─→";
  }
  else {
    cout << "    ";
  }
  cout << "┌┐" << endl;

  cout << "└┘";
  if (g[3][2]) {
    cout << "←─";
  }
  else {
    cout << "    ";
  }
  cout << "└┘" << endl;
}

template<size_t N>
ostream& operator<<(ostream& os, const array<array<ll, N>, N>& g) {
  rep(i, g.size()) {
    rep(j, g[0].size()) {
      if (j) os << " ";
      os << (g[i][j] ? 1 : 0);
    }
    os << endl;
  }
  return os;
}

struct Edge {
  ll a, b;
};

Graph G0 = {};
ll M1, M2 = 1LL<<3;
vector<Edge> edges1, edges2;

Graph get_graph1(ll hash) {
  Graph res = G0;
  rep(i, edges1.size()) {
    if (hash>>i & 1) {
      const Edge& e = edges1[i];
      res[e.a][e.b] = true;
    }
  }
  return res;
}
Graph get_graph2(ll hash) {
  Graph res = G0;
  rep(i, edges2.size()) {
    const Edge& e = edges2[i];
    if (hash>>i & 1) {
      res[e.a][e.b] = true;
    }
    else {
      res[e.b][e.a] = true;
    }
  }
  return res;
}

ll to_hash1(const Graph& g, bool force=false) {
  if (!force) {
    rep(u, 4) rep(v, 4) {
      if (u == v) continue;
      if (g[u][v] && g[v][u]) {
        return -1;
      }
    }
  }
  ll res = 0;
  rep(i, edges1.size()) {
    const Edge& e = edges1[i];
    if (g[e.a][e.b]) {
      res += 1LL<<i;
    }
  }
  return res;
}

Graph merge_graph(const Graph& g1, const Graph& g2) {
  array<array<ll, 6>, 6> G{};
  rep(i, 6) G[i][i] = true;
  rep(u, 4) rep(v, 4) {
    if (g1[u][v]) G[u+2][v+2] = true;
    if (g2[u][v]) G[u][v] = true;
  }
  rep(k, 6) rep(i, 6) rep(j, 6) {
    if (G[i][k] && G[k][j]) {
      G[i][j] = true;
    }
  }
  array<ll, 4> ord{0, 1, 4, 5};
  Graph g = G0;
  rep(u, 4) rep(v, 4) {
    g[u][v] = G[ord[u]][ord[v]];
  }
  return g;
}

void init_edges() {
  rep(i, 4) rep(j, 4) {
    if (i == j) continue;
    edges1.pb({i, j});
  }
  edges2.pb({0, 1});
  edges2.pb({0, 2});
  edges2.pb({1, 3});
}


void solve() {
  ll n; cin >> n >> mod;
  rep(i, 4) G0[i][i] = true;
  init_edges();
  M1 = 1LL<<edges1.size();
  assert(edges1.size() == 12);
  // {
  //   Graph g1 = G0;
  //   Graph g2 = G0;
  //   g1[1][0] = true;
  //   g2[2][0] = true;
  //   g2[0][1] = true;
  //   g2[1][3] = true;
  //   output_graph(g2);
  //   output_graph(g1);
  //   Graph g = merge_graph(g1, g2);
  //   output_graph(g);
  //   cout << to_hash1(g) << endl;
  // }
  // return;
  vector<vector<ll>> merged(M1, vector<ll>(M2));
  rep(i, M1) rep(j, M2) {
    Graph g1 = get_graph1(i);
    Graph g2 = get_graph2(j);
    Graph g = merge_graph(g1, g2);
    merged[i][j] = to_hash1(g);
  }
  // rep(i, M1) {
  //   assert(to_hash1(get_graph1(i), true) == i);
  // }
  // cout << M2 << endl;
  // rep(i, M2) {
  //   output_graph(get_graph2(i));
  // }
  Graph g0 = G0;
  g0[0][2] = g0[2][0] = true;
  g0[1][3] = g0[3][1] = true;
  vector<vector<ll>> dp(n+1, vector<ll>(M1, 0));
  dp[0][to_hash1(g0, true)] = 1;
  rep(i, n) rep(j, M1) {
    if (dp[i][j] == 0) continue;
    rep(k, M2) {
      ll nj = merged[j][k];
      if (nj < 0) continue;
      dp[i+1][nj] = add(dp[i][j], dp[i+1][nj]);
    }
  }
  ll ans = 0;
  rep(i, M1) {
    Graph g = get_graph1(i);
    array<array<ll, 2>, 2> G{};
    rep(j, 4) rep(k, 4) {
      if (g[j][k]) G[j%2][k%2] = true;
    }
    if (g[0][2] || g[2][0] || g[1][3] || g[3][1]) continue;
    if (G[0][1] && G[1][0]) continue;
    if (dp[n][i] == 0) continue;
    // cout << dp[n][i] << endl;
    // output_graph(g);
    // cout << endl;
    ans = add(ans, dp[n][i]);
  }
  cout << ans << endl;
}



Measured memory_bytes: 35360