#include <bits/stdc++.h>
using namespace std;

bool Memory_begin;

/*
-2 0 0 2
-5 -1 -1 1 1 5
-14 -4 -4 0 0 4 4 14
-42 -14 -14 -4 -4 4 4 14 14 42
-132 -48 -48 -20 -20 0 0 20 20 48 48 132
-429 -165 -165 -81 -81 -25 -25 25 25 81 81 165 165 429
-1430 -572 -572 -308 -308 -140 -140 0 0 140 140 308 308 572 572 1430
*/

bool Memory_end;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cerr << (&Memory_end - &Memory_begin) / 1048576.0 << "MB" << '\n';

    int t;
    cin >> t;
    while (t--)
    {
        int n, p, A, B;
        cin >> n >> p;
        vector<int> b(n * 2 + 1), f(n * 2 + 1);
        vector<long long> a(n * 2 + 1);
        cin >> b[0] >> A >> B;
        for (int i = 1; i <= n * 2; i++)
        {
            b[i] = (1ll * A * b[i - 1] % p + B) % p;
            a[i] = a[i - 1] + b[i] + 1;
        }

        vector<int> fac(n * 2 + 1), ifac(n * 2 + 1);
        fac[0] = ifac[0] = 1;
        for (int i = 1; i <= n * 2; i++)
            fac[i] = 1ll * fac[i - 1] * i % p;
        auto inv = [&](int x) -> int
        {
            int y = p - 2, res = 1;
            while (y)
            {
                if (y & 1)
                    res = 1ll * res * x % p;
                x = 1ll * x * x % p;
                y >>= 1;
            }
            return res;
        };
        ifac[n * 2] = inv(fac[n * 2]);
        for (int i = n * 2 - 1; i >= 1; i--)
            ifac[i] = 1ll * ifac[i + 1] * (i + 1) % p;
        auto binom = [&](int x, int y) -> int
        {
            return 1ll * fac[x] * ifac[y] % p * ifac[x - y] % p;
        };
        vector<int> c(n), d(n);
        c[0] = 1;
        for (int i = 1; i < n; i++)
            c[i] = (binom(i * 2, i) + p - binom(i * 2, i + 1)) % p;
        for (int i = 0; i < n; i++)
            d[i] = 1ll * c[i] * c[n - i - 1] % p;
        for (int i = 1; i < n; i++)
            d[i] = (d[i] + d[i - 1]) % p;

        for (int i = 1; i < n * 2; i++)
        {
            int cnt = (2 * n - i - 1) / 2;
            f[i] = (f[i] - d[cnt] + p) % p;
        }
        for (int i = 2; i <= n * 2; i++)
        {
            int cnt = (i - 2) / 2;
            f[i] = (f[i] + d[cnt]) % p;
        }

        int ans = 0;
        for (int i = 1; i <= n * 2; i++)
            ans = (ans + 1ll * a[i] % p * f[i] % p) % p;
        ans = 1ll * ans * inv(d.back()) % p;
        cout << ans << '\n';
    }
}