#include<bits/stdc++.h>
using namespace std;
constexpr int N=1000005;
int qpow(int a,int b,int p)
{
    int res=1;
    while(b)
    {
        if(b&1) res=(long long)res*a%p;
        a=(long long)a*a%p,b>>=1;
    }
    return res;
}
int getinv(int x,int p)
{
    return qpow(x,p-2,p);
}
int n,MOD,A,B;
int a[N*2],b[N*2];
int sum[N*2];
int s[N*2];
int fac[N*2],inv[N*2],ifac[N*2];
int C(int n,int m)
{
    if(m>n) return 0;
    if(m==0||m==n) return 1;
    return (long long)fac[n]*ifac[m]%MOD*ifac[n-m]%MOD;
}
int catalan(int n)
{
    if(n==0||n==1) return 1;
    return (C(2*n,n)-C(2*n,n-1)+MOD)%MOD;
}
void solve()
{
    cin>>n>>MOD>>b[0]>>A>>B;
    inv[1]=1;
    for(int i=2;i<=n*2;i++)
        inv[i]=(long long)(MOD-MOD/i)*inv[MOD%i]%MOD;
    fac[0]=ifac[0]=1;
    for(int i=1;i<=n*2;i++)
    {
        fac[i]=(long long)fac[i-1]*i%MOD;
        ifac[i]=(long long)ifac[i-1]*inv[i]%MOD;
    }
    a[0]=0;
    for(int i=1;i<=n*2;i++)
    {
        b[i]=((long long)b[i-1]*A+B)%MOD;
        a[i]=(a[i-1]+b[i]+1)%MOD;
    }
    for(int i=1;i<=n*2;i++)
        sum[i]=(sum[i-1]+a[i])%MOD;
    for(int i=0;i<=n*2;i++)
        s[i]=((long long)sum[n*2]-sum[i]-sum[n*2-i]+MOD+MOD)%MOD;
    int ans=0;
    for(int len=1;len<=n*2;len++)
        if(len&1) ans=(ans+(long long)catalan((len-1)/2)*catalan((2*n-len-1)/2)%MOD*s[len])%MOD;
    ans=(long long)ans*getinv(catalan(n),MOD)%MOD;
    cout<<ans<<"\n";
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
        solve();
    return 0;
}