#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) { return (ull)rng() % B; }

#line 2 "modint/arbitrary-modint.hpp"

#line 2 "modint/barrett-reduction.hpp"

#include <utility>
using namespace std;

struct Barrett {
    using u32 = unsigned int;
    using i64 = long long;
    using u64 = unsigned long long;
    u32 m;
    u64 im;
    Barrett() : m(), im() {}
    Barrett(int n) : m(n), im(u64(-1) / m + 1) {}
    constexpr inline i64 quo(u64 n) {
        u64 x = u64((__uint128_t(n) * im) >> 64);
        u32 r = n - x * m;
        return m <= r ? x - 1 : x;
    }
    constexpr inline i64 rem(u64 n) {
        u64 x = u64((__uint128_t(n) * im) >> 64);
        u32 r = n - x * m;
        return m <= r ? r + m : r;
    }
    constexpr inline pair<i64, int> quorem(u64 n) {
        u64 x = u64((__uint128_t(n) * im) >> 64);
        u32 r = n - x * m;
        if (m <= r) return {x - 1, r + m};
        return {x, r};
    }
    constexpr inline i64 pow(u64 n, i64 p) {
        u32 a = rem(n), r = m == 1 ? 0 : 1;
        while (p) {
            if (p & 1) r = rem(u64(r) * a);
            a = rem(u64(a) * a);
            p >>= 1;
        }
        return r;
    }
};
#line 4 "modint/arbitrary-modint.hpp"

template <int id> struct ArbitraryModIntBase {
    int x;

    ArbitraryModIntBase() : x(0) {}

    ArbitraryModIntBase(int64_t y) {
        int z = y % get_mod();
        if (z < 0) z += get_mod();
        x = z;
    }

    ArbitraryModIntBase &operator+=(const ArbitraryModIntBase &p) {
        if ((x += p.x) >= get_mod()) x -= get_mod();
        return *this;
    }

    ArbitraryModIntBase &operator-=(const ArbitraryModIntBase &p) {
        if ((x += get_mod() - p.x) >= get_mod()) x -= get_mod();
        return *this;
    }

    ArbitraryModIntBase &operator*=(const ArbitraryModIntBase &p) {
        x = rem((unsigned long long)x * p.x);
        return *this;
    }

    ArbitraryModIntBase &operator/=(const ArbitraryModIntBase &p) {
        *this *= p.inverse();
        return *this;
    }

    ArbitraryModIntBase operator-() const { return ArbitraryModIntBase(-x); }
    ArbitraryModIntBase operator+() const { return *this; }

    ArbitraryModIntBase operator+(const ArbitraryModIntBase &p) const { return ArbitraryModIntBase(*this) += p; }

    ArbitraryModIntBase operator-(const ArbitraryModIntBase &p) const { return ArbitraryModIntBase(*this) -= p; }

    ArbitraryModIntBase operator*(const ArbitraryModIntBase &p) const { return ArbitraryModIntBase(*this) *= p; }

    ArbitraryModIntBase operator/(const ArbitraryModIntBase &p) const { return ArbitraryModIntBase(*this) /= p; }

    bool operator==(const ArbitraryModIntBase &p) const { return x == p.x; }

    bool operator!=(const ArbitraryModIntBase &p) const { return x != p.x; }

    ArbitraryModIntBase inverse() const {
        int a = x, b = get_mod(), u = 1, v = 0, t;
        while (b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ArbitraryModIntBase(u);
    }

    ArbitraryModIntBase pow(int64_t n) const {
        ArbitraryModIntBase ret(1), mul(x);
        while (n > 0) {
            if (n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const ArbitraryModIntBase &p) { return os << p.x; }

    friend istream &operator>>(istream &is, ArbitraryModIntBase &a) {
        int64_t t;
        is >> t;
        a = ArbitraryModIntBase(t);
        return (is);
    }

    int get() const { return x; }

    inline unsigned int rem(unsigned long long p) { return barrett().rem(p); }

    static inline Barrett &barrett() {
        static Barrett b;
        return b;
    }

    static inline int &get_mod() {
        static int mod = 0;
        return mod;
    }

    static void set_mod(int md) {
        assert(0 < md && md <= (1LL << 30) - 1);
        get_mod() = md;
        barrett() = Barrett(md);
    }
};

using ArbitraryModInt = ArbitraryModIntBase<-1>;

/**
 * @brief modint (2^{30} 未満の任意 mod 用)
 */

// ax+by = gcd(a,b) の整数解を求める
// |x| <= |b|, |y| <= |a|
// https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_E
ll extgcd(ll a, ll b, ll &x, ll &y) {
    ll d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= a / b * x;
    } else {
        x = 1, y = 0;
    }
    return d;
}
// a^-1 (mod b) を求める
ll modinv(ll a, ll b) {
    assert(gcd(a, b) == 1);
    ll x, y;
    extgcd(a, b, x, y);
    return (x + b) % b;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int q;
    cin >> q;
    while (q--) {
        int n, mod;
        cin >> n >> mod;
        ArbitraryModInt::set_mod(mod);
        ArbitraryModInt b, A, B;
        cin >> b >> A >> B;
        vector<ArbitraryModInt> C(n + 1);
        C[0] = 1;
        for (int i = 1; i <= n; ++i) {
            C[i] = C[i - 1] * ArbitraryModInt(i + 1).inverse() * (4 * i - 2);
        }
        ArbitraryModInt res = 0, cnt = 0;
        ArbitraryModInt a = 0;
        for (int i = 1; i <= 2 * n; ++i) {
            b = (A * b + B);
            a += b + 1;
            if (i % 2 == 0) {
                cnt += C[i / 2 - 1] * C[n - i / 2];
            }
            res += (cnt * 2 - C[n] + mod) * a;
        }
        cout << res / C[n] << "\n";
    }
}