#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T> void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T> void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

const int maxn = 3000010;

int n, a[4], mod, iv2, ans;

inline void add(int &x, int y) { x += y; if (x >= mod) x -= mod; }
inline void sub(int &x, int y) { x -= y; if (x < 0) x += mod; }
inline int Add(int x, int y) { x += y; if (x >= mod) x -= mod; return x; }
inline int Sub(int x, int y) { x -= y; if (x < 0) x += mod; return x; }

struct Complex {
  int a, b;
  // a + bi
  Complex() { a = b = 0; }
  Complex(int x, int y) { a = x, b = y; }
  friend Complex operator+(Complex x, Complex y) { return Complex(Add(x.a, y.a), Add(x.b, y.b)); }
  friend Complex operator-(Complex x, Complex y) { return Complex(Sub(x.a, y.a), Sub(x.b, y.b)); }
  friend Complex operator*(Complex x, Complex y) { return Complex(Sub(1ll * x.a * y.a % mod, 1ll * x.b * y.b % mod), Add(1ll * x.a * y.b % mod, 1ll * x.b * y.a % mod)); }
} w[4], iw[4], pw[4][4][maxn], piw[4][maxn];

Complex fpw(Complex a, ll p) {
  Complex res = Complex(1, 0);
  while (p) {
    if (p & 1) res = res * a;
    a = a * a, p >>= 1;
  }
  return res;
}

void work() {
  cin >> n, ans = 0;
  rep (i, 0, 3) cin >> a[i];
  Complex sum = Complex();
  rep (x, -1, 3) rep (y, -1, 3) {
    if (x != -1 && !a[x]) continue;
    if (y != -1 && !a[y]) continue;
    if (x != -1 && x == y && a[x] <= 1) continue;
    // i 在 x，-i 在 y
    int rest = n - (x != -1) - (y != -1);
    if (rest < 0) continue;
    for (int p : {0, 2}) {
      if (!rest && p == 2) continue;
      Complex t = fpw((w[p] * w[p] + Complex(1, 0)) * Complex(iv2, 0), 1ll * rest * (rest - 1) / 2);
      if (x != -1) t = t * pw[p][1][rest];
      if (y != -1) t = t * pw[p][3][rest];
      if (x != -1 && y != -1) t = t * ((w[1] * w[3] + Complex(1, 0)) * Complex(iv2, 0));
      if (x != -1 && y != -1) {
        if (x == y) t = t * Complex(1ll * a[x] * (a[x] - 1) % mod, 0);
        else t = t * Complex(1ll * a[x] * a[y] % mod, 0);
      } else if (x != -1) {
        t = t * Complex(a[x], 0);
      } else if (y != -1) {
        t = t * Complex(a[y], 0);
      }
      static int b[4];
      rep (i, 0, 3) b[i] = a[i];
      if (x != -1) b[x]--;
      if (y != -1) b[y]--;
      rep (i, 0, 3) t = t * piw[p][i * b[i]];
      if (x != -1) t = t * piw[1][x];
      if (y != -1) t = t * piw[3][y];
      // cerr << x << " " << y << " " << p << " " << t.a << " " << t.b << endl;
      sum = sum + t;
    }
  }
  // cerr << sum.a << " + " << sum.b << "i\n";
  rep (i, 1, n) sum = sum * Complex(iv2, 0), sum = sum * Complex(iv2, 0);
  cout << sum.a << '\n';
}

int main() {
  // freopen("in", "r", stdin);
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  int t; cin >> t >> mod, iv2 = (mod + 1) >> 1;
  w[0] = Complex(1, 0), w[1] = Complex(0, 1);
  w[2] = Complex(mod - 1, 0), w[3] = Complex(0, mod - 1);
  iw[0] = Complex(1, 0), iw[1] = Complex(0, mod - 1);
  iw[2] = Complex(mod - 1, 0), iw[3] = Complex(0, 1);
  rep (i, 0, 3) if (i & 1) {
    piw[i][0] = Complex(1, 0);
    rep (j, 1, maxn - 1) piw[i][j] = piw[i][j - 1] * iw[i];
  }
  rep (i, 0, 3) if (!(i & 1)) rep (j, 0, 3) if (j & 1) {
    Complex cur = (w[i] * w[j] + Complex(1, 0)) * Complex(iv2, 0);
    pw[i][j][0] = Complex(1, 0);
    rep (k, 1, 1000000) pw[i][j][k] = pw[i][j][k - 1] * cur;
  }
  // cerr << 1. * clock() / CLOCKS_PER_SEC << endl;
  while (t--) work();
}