#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 2e6+10; int mod;
int addv(int x,int y){return (x+y>=mod)?(x+y-mod):(x+y);}
int subv(int x,int y){return (x>=y)?(x-y):(x-y+mod);}
void add(int& x,int y){x = addv(x,y);}
void sub(int& x,int y){x = subv(x,y);}
int qpow(int a,int n){
    int res = 1; a%=mod;
    while(n){
        if(n&1)res = 1ll*res*a%mod;
        n>>=1; a = 1ll*a*a%mod;
    }
    return res;
}
int qinv(int a){return qpow(a,mod-2);}
//
int T,n,a[N],b[N],A,B,ans,sum;
int fac[N],rfac[N],pre[N];
int C(int n,int m){
    if(m<0 || n<m)return 0;
    return 1ll*fac[n]*rfac[m]%mod*rfac[n-m]%mod;
}
int C(int n){ //catlan(n)
    return subv(C(2*n,n),C(2*n,n+1));
}

void solve(){
    cin>>n>>mod>>b[0]>>A>>B;
    for(int i=1;i<=2*n;i++)b[i] = (1ll*A*b[i-1]+B)%mod,a[i] = a[i-1] + b[i] + 1;

    fac[0] = 1; for(int i=1;i<=2*n;i++)fac[i] = fac[i-1]*i%mod;
    rfac[2*n] = qinv(fac[2*n]); for(int i=2*n-1;i>=0;i--)rfac[i] = rfac[i+1]*(i+1)%mod;

    ans = sum = 0;
    for(int i=1;i<=2*n;i++)sum = (sum + a[i])%mod; sum = sum * C(n)%mod;
    pre[0] = C(n-1); for(int i=1;i<=n-1;i++)pre[i] = (pre[i-1] + C(i) * C(n-1-i))%mod;

    for(int i=2;i<=2*n;i++){  //位置i是右括号的方案数
        int res;
        if(i&1)res = pre[(i-3)/2];
        else res = pre[(i-2)/2];
        add(ans,res*2*a[i]%mod);
    }
    sub(ans,sum);
    ans = ans*qinv(C(n))%mod;
    cout<<ans<<endl;
}

signed main(){
    cin>>T;
    while(T--)solve();

    return 0;
}