#include<bits/stdc++.h>
using namespace std;
int T,P,n,a[4];
struct Fastmod{
typedef __uint128_t uLL;
typedef unsigned long long ull;
ull P,m;
void init(ull P){
	this->P=P,m=(uLL(1)<<64)/P;
}
ull mod(ull a){
	ull b=uLL(a)*m>>64;
	ull r=a-b*P;
	return r>=P?r-P:r;
}
}Z;
struct comp{
	int a,b;
	comp operator +(comp x){return {Z.mod(a+x.a),Z.mod(b+x.b)};}
	comp operator +(int x){return {Z.mod(a+x),b};}
	comp operator *(int x){return {Z.mod(1ll*x*a),Z.mod(1ll*x*b)};}
	comp operator *(comp x){return {Z.mod(1ll*a*x.a+1ll*(P-b)*x.b),Z.mod(1ll*a*x.b+1ll*b*x.a)};}
}I,_I,ans;
int ksm(int x,long long y){
	int res=1;
	for(;y;y>>=1,x=Z.mod(1ll*x*x))if(y&1)res=Z.mod(1ll*res*x);
	return res;
}
comp ksm(comp x,long long y){
	comp res={1,0};
	for(;y;y>>=1,x=x*x)if(y&1)res=res*x;
	return res;
}
void solve(){
	scanf("%d",&n);
	for(int i=0;i<4;++i)scanf("%d",&a[i]);
	ans={1+(a[1]+a[3]&1?-1:1),0},I={0,1},_I={0,P-1};
	for(int i=0;i<4;++i)if(a[i]){
		ans=(ans+ksm(_I,i)*ksm((I+1)*(P+1>>1),n-1)*a[i]);
		ans=(ans+ksm(_I,i)*(a[1]+a[3]+i&1?P-1:1)*ksm((_I+1)*(P+1>>1),n-1)*a[i]);
		ans=(ans+ksm(I,i)*ksm((_I+1)*(P+1>>1),n-1)*a[i]);
		ans=(ans+ksm(I,i)*(a[1]+a[3]+i&1?P-1:1)*ksm((I+1)*(P+1>>1),n-1)*a[i]);
	}
	for(int i=0;i<4;++i)for(int j=0;j<4;++j){
		int w;
		if(i!=j)w=Z.mod(1ll*a[i]*a[j]);
		else w=Z.mod(1ll*a[i]*(a[i]-1));
		if(!w||a[1]+a[3]+j+i&1)continue;
		ans=(ans+ksm(_I,i)*ksm(I,j)*ksm((I+1)*(P+1>>1),n-2)*ksm((_I+1)*(P+1>>1),n-2)*2*w);
	}
	printf("%d\n",Z.mod(1ll*ksm(P+1>>1,2*n)*ans.a));
}
int main(){
	scanf("%d%d",&T,&P);
	Z.init(P);
	while(T--)solve();
	return 0;
}