//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
//#pragma GCC optimize("Ofast","unroll-loops","inline")
#include<bits/stdc++.h>
#define ll long long
#define int ll
#define pb push_back
#define pii pair<int,int>
#define MP make_pair
#define fi first
#define se second
using namespace std;
const int N=2e6+10,M=1e6+10;
int mod;
inline void Add(int &x,int y){x+=y;if(x>=mod) x-=mod;}
inline void Del(int &x,int y){x-=y;if(x<0) x+=mod;}
inline int del(int x,int y){x-=y;return x<0?x+mod:x;}
inline int add(int x,int y){x+=y;return x>=mod?x-mod:x;}
int fac[N],ifac[N],inv[N];
inline int C(int n,int m){
	if(n<0||m<0||n<m) return 0;
	return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		a=1ll*a*a%mod;b>>=1;
	}return res;
}
inline int H(int n){return 1ll*C(n,n/2)*inv[n/2+1]%mod;}
int a[N],b[N],s[N],n,A,B;
void solve(){
	cin>>n>>mod>>b[0]>>A>>B;
	fac[0]=ifac[0]=ifac[1]=1;for(int i=1;i<=2*n;i++) fac[i]=1ll*fac[i-1]*i%mod;
	ifac[2*n]=qpow(fac[2*n],mod-2);for(int i=2*n;i;i--) ifac[i-1]=1ll*ifac[i]*i%mod;
	inv[0]=0;for(int i=1;i<N;i++) inv[i]=1ll*ifac[i]*fac[i-1]%mod;
	a[0]=0;
	for(int i=1;i<=2*n;i++){
		b[i]=(1ll*A*b[i-1]+B)%mod;
		a[i]=a[i-1]+b[i]+1;
		s[i]=(s[i-1]+a[i])%mod;
	}
	int ans=0;
	for(int j=2*n;j>0;j-=2){
		int res=1ll*H(2*n-j)*H(j-2)%mod;
		Del(ans,1ll*res*s[j-1]%mod);
	}
	for(int j=1;j<=2*n;j+=2){
		int res=1ll*H(j-1)*H(2*n-j-1)%mod;
		int val=del(s[2*n],s[j]);
			Add(ans,1ll*res*val%mod);
	}
	int iv=qpow(H(2*n),mod-2);
	cout<<iv*ans%mod<<'\n';
}
signed main(){
//	freopen("b.in","r",stdin);
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int T;cin>>T;
	while(T--) solve();
	return 0;
}