#include <bits/stdc++.h>

int N, P, S, A, B;
long long a[1100000], b[1100000];

long long fpow(long long a, long long b, long long p) {
    long long s = 1;
    for (; b; b >>= 1, a = a * a % p)
        if (b & 1) s = s * a % p;
    return s;
}

long long fac[2100000], inv[2100000];

long long catalan(int n) { return fac[2 * n] * inv[n] % P * inv[n + 1] % P; }

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d%d%d", &N, &P, &S, &A, &B);

        fac[0] = inv[0] = 1;
        for (int i = 1; i <= 2 * N; ++i) fac[i] = fac[i - 1] * i % P;
        for (int i = 1; i <= 2 * N; ++i) inv[i] = fpow(fac[i], P - 2, P);

        a[0] = 0;
        b[0] = S;
        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;
            // printf("%d %lld\n", i, a[i]);
        }

        static long long cnt[2100000];
        cnt[1] = catalan(N);
        for (int i = 2; i <= N; ++i) {
            if (!(i & 1)) {
                cnt[i] = (cnt[i - 1] - catalan(N - i / 2) * catalan(i / 2 - 1) + P) % P;
            } else {
                cnt[i] = cnt[i - 1];
            }
        }
        if (N % 2 == 0) {
            cnt[N] = cnt[1] * fpow(2, P - 2, P) % P;
        }
        for (int i = N + 1; i <= 2 * N; ++i) {
            cnt[i] = (cnt[1] - cnt[2 * N + 1 - i] + P) % P;
        }
        // for (int i = 1; i <= 2 * N; ++i) {
            // printf("%lld\n", cnt[i]);
        // }

        long long ans = 0;
        for (int i = 1; i <= 2 * N; ++i) {
            ans = (P + ans - cnt[i] * a[i] % P) % P;
            ans = (ans + (P + cnt[1] - cnt[i]) % P * a[i] % P) % P;
        }

        printf("%lld\n", ans * fpow(cnt[1], P - 2, P) % P);
    }
}