#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

#define N 2000010
int fac[N], inv[N];
int a[N], b[N];
int f[N], g[N];
int n, P, A, B;
int C(int n, int m) {return 1LL * fac[n] * inv[m] % P * inv[n - m] % P;}
int qpow(int a, int b)
{
    int ans = 1;
    while (b) {if (b & 1) ans = 1LL * ans * a % P; b >>= 1; a = 1LL * a * a % P;}
    return ans;
}
void sol()
{  
    cin >> n >> P >> b[0] >> A >> B;
    for (int i = 1; i <= 2 * n; i ++)
    {
        b[i] = (1LL * A * b[i - 1] + B) % P;
        a[i] = (a[i - 1] + b[i] + 1) % P;
    }
    fac[0] = 1;
    for (int i = 1; i <= 2 * n; i ++) fac[i] = 1LL * fac[i - 1] * i % P;
    inv[0] = inv[1] = 1;
    for (int i = 2; i <= 2 * n; i ++) inv[i] = 1LL * (P - P / i) * inv[P % i] % P;
    for (int i = 2; i <= 2 * n; i ++) inv[i] = 1LL * inv[i] * inv[i - 1] % P;

    f[0] = 1;
    for (int i = 1; i <= n; i ++)f[i] = (C(2 * i, i) + P - C(2 * i, i - 1)) % P;
    for (int i = 0; i <= n - 1; i ++)g[i] = 1LL * f[i] * f[(2 * n - 2 - i * 2) / 2] % P;
    for (int i = 0; i <= n - 1; i ++)g[i] = (g[i] + (i ? g[i - 1] : 0)) % P;
    int ans = 0;
    // cout << "??:" << g[0] << endl;
    // for (int i = 1; i <= 2 * n; i ++) cout << a[i] << ' '; cout << endl;
    for (int i = 1; i <= 2 * n; i ++)
    {
        int t = (2 * n - i - 1) / 2;
        // cout << "EEE:" << i << ' ' << (2 * n - i - 1) / 2 << ' ' << (i - 2) / 2 << '\n';
        if (i < 2 * n)ans = (ans + 1LL * (P - a[i]) * g[t]) % P;

        t = (i - 2) / 2;
        if (i > 1)ans = (ans + 1LL * a[i] * g[t]) % P;
    }  

    ans = 1LL * ans * qpow(f[n], P - 2) % P;
    cout << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    cin >> T;
    while (T --) sol();
    return 0;
}