#include<iostream>
#include<cstdio>
//#define int long long
typedef long long ll;
using namespace std;
const int N=2e6+9;
int mod;
ll fac[N],inv[N],ifac[N];
void ycl(int lim)
{
	fac[0]=inv[0]=ifac[0]=fac[1]=inv[1]=ifac[1]=1;
	for(int i=2;i<=lim;i++)
	{
		fac[i]=fac[i-1]*i%mod;
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
		ifac[i]=ifac[i-1]*inv[i]%mod;
	}
}
inline ll C(int x,int y){return x>=y&&y>=0?fac[x]*ifac[y]%mod*ifac[x-y]%mod:0;}
inline ll f(int n){return (C(n+n,n)-C(n+n,n-1)+mod)%mod;}
inline int ksm(ll x,int y){int z=1;for(;y;x=x*x%mod,y>>=1) if(y&1) z=z*x%mod;return z;}
ll n,p,b[N],a[N],A,B;
ll suma[N]; 
inline ll md(ll x){if(x>=mod)return x-mod;return x;}
void work()
{
	scanf("%lld%d%lld%lld%lld",&n,&mod,&b[0],&A,&B);
//	n=1e6,mod=998244353,b[0]=3,A=33,B=333;
	ycl(n*2);
	for(int i=1;i<=2*n;i++)
	{
		b[i]=(A*b[i-1]+B)%mod;
		a[i]=md(a[i-1]+b[i]+1);
	}
	suma[n*2+1]=0;
	for(int i=2*n;i>=1;i--) suma[i]=md(suma[i+1]+a[i]);
	__int128 ans=0;
	for(int i=0;i<n*2;i+=2)
	{
		ans+=(__int128)f(i/2)*f((n*2-i)/2-1)*suma[i+2];
	}
	for(int i=1,j=n*2;i<j;i++,j--) swap(a[i],a[j]);
	suma[n*2+1]=0;
	for(int i=2*n;i>=1;i--) suma[i]=md(suma[i+1]+a[i]);
	for(int i=0;i<n*2;i+=2)
	{
		ans-=(__int128)f(i/2)*f((n*2-i)/2-1)*suma[i+2];
	}
	ans=(ans%mod+mod)%mod;
	ll xx=ans;
	printf("%lld\n",xx*ksm(f(n),mod-2)%mod);
}
signed main()
{
	int T=10;
	scanf("%lld",&T);
	while(T--) work();
}