#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const int N=2e6+5;
int n,Mod,A,B;
int a[N],b[N],H[N],F[N],inv[N];
inline int qpow(int x,int y,int z=1){
	for(;y;(y>>=1)&&(x=(LL)x*x%Mod))if(y&1)z=(LL)z*x%Mod;return z;
}
inline void MAIN(){
	cin>>n>>Mod>>b[0]>>A>>B;
	for(int i=1;i<=n+n;++i)
		b[i]=(1ll*b[i-1]*A+B)%Mod,a[i]=(a[i-1]+b[i]+1)%Mod;
	inv[1]=1;
	for(int i=2;i<=n+1;++i)
		inv[i]=(Mod-Mod/i*(LL)inv[Mod%i]%Mod);
	H[0]=1;
	for(int i=1;i<=n;++i)
		H[i]=(4*i-2ll)*H[i-1]%Mod*inv[i+1]%Mod;
	for(int i=1;i<=n;++i)
		F[i]=(F[i-1]+1ll*H[n-i]*H[i-1])%Mod;
	int ans=0;
	for(int i=1;i<=n+n;++i)
		ans=(ans+(H[n]-F[(n+n-i+1)/2]*2ll)*a[i])%Mod;
	ans=qpow(H[n],Mod-2,ans);
	cout<<(ans<0?ans+Mod:ans)<<'\n';
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
	int t=1;cin>>t;while(t--)MAIN();
    return 0;
}
/*
5
1 1000000007 0 1 0
2 1000000007 0 1 1
2 7 5 2 3
3 31 15 6 24
20 1000000007 0 1 0
*/