#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=2e6+5;
int n,p;
ll F[N],I[N];
inline ll ksm(ll x){ll r=1;for(int y=p-2;y;y>>=1,x=x*x%p)if(y&1)r=r*x%p;return r;}
inline ll C(int n,int m){return m<0||n<m?0:F[n]*I[m]%p*I[n-m]%p;}

inline void slv(){
	ll a0=0,b0,A,B;
	scanf("%d%d%lld%lld%lld",&n,&p,&b0,&A,&B);
	F[0]=1;for(int i=1;i<=n*2;i++)F[i]=F[i-1]*i%p;
	I[n*2]=ksm(F[n*2]);for(int i=n*2-1;~i;i--)I[i]=I[i+1]*(i+1)%p;
	ll rs=0,tt=F[n*2]*I[n]%p*I[n+1]%p;
	for(int i=1;i<=n*2;i++){
		b0=(A*b0+B)%p;a0=(a0+b0+1)%p;
		ll x=0;
		for(int j=i-1;j>=0;j-=2)x=(x+(C(i-1,i+j-1>>1)-C(i-1,i+j+1>>1)+p)*(C(n*2-i,n*2-i+j+1>>1)-C(n*2-i,n*2-i+j+3>>1)+p))%p;
		rs=(rs+x*(p-a0)+(tt-x+p)*a0)%p;
	}
	printf("%lld\n",rs*ksm(tt)%p);
}
int main(){
	int T;scanf("%d",&T);while(T--)slv();
	return 0;
}