#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
void solve(){
	int n,mod,A,B,ans=0;
	cin>>n>>mod;
	vector<int> b(n*2+1),a(n*2+1),iv(n+2),c(n+1),f(n*2+1);
	cin>>b[0]>>A>>B;
	for(int i=1;i<=n*2;i++) b[i]=(1ll*A*b[i-1]+B)%mod,a[i]=(a[i-1]+b[i]+1)%mod;
	iv[1]=1;c[0]=c[1]=1;
	for(int i=2;i<=n+1;i++) iv[i]=1ll*(mod-mod/i)*iv[mod%i]%mod;
	for(int i=2;i<=n;i++) c[i]=(4ll*i-2)*iv[i+1]%mod*c[i-1]%mod;
	for(int i=2;i<=n*2;i++){
		int t=i/2-1;
		f[i]=(f[i-2]+1ll*c[t]*c[n-t-1])%mod;
	}
	for(int i=1;i<=n*2;i++){
		if(i>1) (ans+=1ll*a[i]*f[i]%mod)%=mod;
		if(i<n*2) (ans+=mod-1ll*a[i]*f[n*2-i+1]%mod)%=mod;
	}
	for(int x=c[n],y=mod-2;y;y>>=1,x=1ll*x*x%mod) if(y&1) ans=1ll*ans*x%mod;
	cout<<ans<<"\n";
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}