#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using vi=vector<int>;
using vl=vector<ll>;
using pii=pair<int,int>;
#define all(a) begin(a),end(a)
#define pb push_back

const int N=10000010,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;

int t,n,p,b0,A,B,fac[N],inf[N],a[N],b[N],ps[N],cat[N];

int mul(int a,int b,int p)
{
	return (a*1ll*b)%p;
}

int add(ll a,ll b,int p)
{
	if (a+b>=p) return a+b-p;
	return a+b;
}

int sub(int a,int b,int p)
{
	if (a<b) return a-b+p;
	return a-b;
}

int pot(int n,int k,int p)
{
	if (k==0) return 1;
	int r=pot(n,k/2,p);
	r=mul(r,r,p);
	if (k%2) r=mul(r,n,p);
	return r;
}

int cho(int a,int b,int p)
{
	if (b>a || b<0) return 0;
	return mul(fac[a],mul(inf[b],inf[a-b],p),p);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>t;
	while (t--)
	{
		cin>>n>>p>>b0>>A>>B;
		fac[0]=1;
		for (int i=1;i<=2*n;++i) fac[i]=mul(fac[i-1],i,p);
		inf[2*n]=pot(fac[2*n],p-2,p);
		for (int i=2*n-1;i>=0;--i) inf[i]=mul(inf[i+1],i+1,p);
		for (int i=0;i<=n;++i) cat[i]=sub(cho(2*i,i,p),cho(2*i,i-1,p),p);
		for (int i=1;i<=n;++i) ps[i]=add(ps[i-1],mul(cat[i-1],cat[n-i],p),p);
		b[0]=b0;
		int an=0;
		for (int i=1;i<=2*n;++i)
		{
			b[i]=add(mul(A,b[i-1],p),B,p);
			a[i]=add(add(a[i-1],b[i],p),1,p);
			an=add(an,mul(a[i],sub(2*ps[i/2],ps[n],p),p),p);
		}
		cout<<mul(an,pot(ps[n],p-2,p),p)<<en;
	}
}