#include <bits/stdc++.h>
#define rep(i, f, t) for(int i(f); i <= t; ++i)
#define re(i, t) for(int i(1); i <= t; ++i)
#define per(i, t, f) for(int i(t); i >= f; --i)
#define pe(i, t) for(int i(t); i >= 1; --i) 
#define nx(i, u) for(int i(head[u]); i; i = e[i].nxt)
typedef long long ll;
typedef unsigned long long ull; 
using namespace std;
typedef pair <int, int> pii;
#define pb push_back
#define eb emplace_back 
#define fi first
#define se second
#define ix(l, r) ((l + r) | (l != r))  
#define mp(i, j) (make_pair(i, j))
//#define int long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
namespace IO {
char buf[1 << 21], *p1 = buf, *p2 = buf, buf1[1 << 21];
inline char gc() {return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;}
template<class I>
inline void read(I &x) {x = 0;I f = 1;char c = gc();while (c < '0' || c > '9') {if (c == '-') {f = -1;} c = gc();}while (c >= '0' && c <= '9') {x = x * 10 + c - '0';c = gc();}x *= f;}
template<class I>
inline void write(I x) {if (x == 0) {putchar('0');return;}I tmp = x > 0 ? x : -x;if (x < 0) {putchar('-');}int cnt = 0;while (tmp > 0) {buf1[cnt++] = tmp % 10 + '0';tmp /= 10;}while (cnt > 0)putchar(buf1[--cnt]);}
#define outn(x) write(x), putchar('\n')
#define out(x) write(x), putchar(' ')
} using namespace IO;
#define look_memory cerr<<abs(&sT-&eD)/1024.0/1024<<'\n'
int sT;

int T, mod;
int val[5], n;

void MOD (int &x) {
	x = x >= mod ? x - mod : x;
}

struct cp {

	int a, b;
	cp operator + (const cp &rhs) {cp c; MOD(c.a = a + rhs.a), MOD(c.b = b + rhs.b); return c;}
	cp operator - (const cp &rhs) {cp c; MOD(c.a = a + mod - rhs.a), MOD(c.b = b + mod - rhs.b); return c;}
	cp operator * (const cp &rhs) {cp c; MOD(c.a = 1ll * a * rhs.a % mod + mod - 1ll * b * rhs.b % mod), MOD(c.b = 1ll * a * rhs.b % mod + 1ll * b * rhs.a % mod); return c;}
	cp operator * (const int &v)  {cp c; c.a = 1ll * a * v % mod, c.b = 1ll * b * v % mod; return c;}
	cp(int x=0,int y=0) {a=x,b=y;}

}w[5];

cp ksm (cp a, int b) {
	if(!b) return cp(1,0);
	cp ans=a, base=a;
	--b;
	while(b) {
		if(b&1) ans = ans * base;
		base = base * base;
		b >>= 1;
	}
	return ans;
}

int ksm (int a, int b) {
	ll ans = 1, base = a;
	while(b) {
		if(b & 1) ans = ans * base % mod;
		base = base * base % mod;
		b >>= 1;
	}
	return ans;
}

void solve () {
	cp ans;
	int inv2 = (mod+1)/2;
	cp x[2], y[2];
	x[0] = cp(inv2, inv2), x[1] = cp(inv2, mod-inv2);
	y[0] = ksm(x[0], n-2), y[1] = ksm(x[1], n-2);
	rep(i, 0, 4) {
		int tmp = 1;
		if(i < 4) tmp = val[i];
		--val[i];
		rep(j, 0, 4) {
			int lst = tmp;
			if(j < 4) tmp = 1ll * tmp * val[j] % mod;
			--val[j];
			int op = 0;
			rep(k, 0, 3) if(val[k] < 0) op = 1;
			if(!op){
			rep(k, 0, 1) {
				cp res;
				int sz = 0;
				rep(l, 0, 3) {
					sz += val[l] * l;
				}
				res.a = ((k&1) && (sz&1)) ? (mod - 1) : 1;
				if(i < 4 && i) res = res * w[3-i+1];
				if(j < 4 && j) res = res * w[j];
				if(i < 4) { 
					if(j < 4) res = res * y[0] * y[1];
					else res = res * y[k] * x[k];
				}
				else if(j < 4) res = res * y[k^1] * x[k^1];
				ans = ans + res * tmp;
			}}
			++val[j];
			tmp = lst;
		}
		++val[i];
	} 
	int lc = 1ll * ans.a * ksm(ksm(4, n), mod-2) % mod;
	outn(lc);
}

int main () {
	read(T), read(mod);
	w[0] = cp(1,0), w[1] = cp(0,1), w[2] = cp(mod-1,0), w[3] = cp(0,mod-1);
	while(T--) {
		read(n);
		rep(i, 0, 3) read(val[i]);
		solve();			 
	}
	return 0;
}