#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;
}