#include<bits/stdc++.h>
using namespace std;
int P;
long long qpow(long long a,long long b)
{
	long long ans=1;
	while(b)
	{
		if(b&1)ans=ans*a%P;
		a=a*a%P,b>>=1;
	}
	return ans;
}
struct cp
{
	long long a,b;
	cp(){}cp(int x){a=x,b=0;}cp(int x,int y){a=x,b=y;}
	cp operator+(const cp&A)const{return cp((a+A.a)%P,(b+A.b)%P);}
	cp operator-()const{return cp((P-a),(P-b));}
	cp operator-(const cp&A)const{return cp((a+P-A.a)%P,(b+P-A.b)%P);}
	cp operator*(const cp&A)const{return cp((a*A.a+P-b*A.b%P)%P,(b*A.a+a*A.b)%P);}
	cp operator*(const long long&x)const{return cp(a*x%P,b*x%P);}
};
cp qpow(cp a,long long b)
{
	cp ans=1;
	while(b)
	{
		if(b&1)ans=ans*a;
		a=a*a,b>>=1;
	}
	return ans;
}
int a[4];
int main()
{
	int T,n;
	cin>>T>>P;
	const cp I(0,1),inv2(P+1>>1,0),X(1,0);
	while(T--)
	{
		cin>>n>>a[0]>>a[1]>>a[2]>>a[3];
		//no i
		int o=a[1]+a[3]&1;
		cp ans={(o?0:2),0};
		for(int i=0;i<4;++i)if(a[i])
		{
			ans=ans+qpow(I,i)*qpow((X-I)*inv2,n-1)*a[i];//i1
			ans=ans+qpow(I,i)*qpow((X+I)*inv2,n-1)*a[i]*(o^(i&1)?P-1:1);//i-1
			ans=ans+qpow(-I,i)*qpow((X+I)*inv2,n-1)*a[i];//-i1
			ans=ans+qpow(-I,i)*qpow((X-I)*inv2,n-1)*a[i]*(o^(i&1)?P-1:1);//-i-1
		}
		for(int i=0;i<4;++i)if(a[i])//ch i
			for(int j=0;j<4;++j)if(a[j]>(i==j))//ch -i
			{
				
				if(o^(i+j&1))continue;
				long long F=1ll*a[i]*(a[j]-(i==j))%P;
				ans=ans+qpow(-I,i)*qpow(I,j)*qpow((I+X)*inv2,n-2)*qpow((X-I)*inv2,n-2)*2*F;
			}
		long long AL=ans.a*qpow(P+1>>1,2*n)%P;
		cout<<AL<<endl;
	}
}