#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int T,n,MOD,A,B,ans,a[N],b[N],s[N],fc[N],invfc[N];
int qpow(int x,int y)
{
    int res=1;
    for(;y;y/=2,x=1ll*x*x%MOD) if(y&1)
        res=1ll*res*x%MOD;return res;
}
void init(int n)
{
    fc[0]=1;for(int i=1;i<=n;++i) fc[i]=fc[i-1]*i%MOD;
    invfc[n]=qpow(fc[n],MOD-2);
    for(int i=n;i;--i) invfc[i-1]=invfc[i]*i%MOD;
}
int bn(int x,int y) {return x<y || y<0?0:fc[x]*invfc[y]%MOD*invfc[x-y]%MOD;}
int cat(int x) {return x?(bn(x*2,x)-bn(x*2,x-1)+MOD)%MOD:1;}
void slv()
{
    scanf("%lld %lld %lld %lld %lld",&n,&MOD,&b[0],&A,&B);ans=0;init(n*2);
    for(int i=1;i<=n*2;++i) b[i]=(A*b[i-1]+B)%MOD,a[i]=(a[i-1]+b[i]+1)%MOD;
    for(int i=1;i<=n*2;++i) s[i]=(s[i-1]+a[n*2-i+1]-a[i]+MOD)%MOD;
    for(int i=0;i<n;++i) ans=(ans+cat(i)*cat(n-i-1)%MOD*s[i*2+1])%MOD;
    ans=1ll*ans*qpow(cat(n),MOD-2)%MOD;printf("%d\n",ans);
}
signed main()
{
    scanf("%d",&T);
    while(T--) slv();return 0;
}