#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 2e6 + 5;
int mod;
int fac[N], inv[N], Inv[N], cat[N];
int ans[N];
int qpow(int x, int y)
{
	int ans = 1;
	while(y)
	{
		if(y & 1)
			ans = (ll)ans * x % mod;
		x = (ll)x * x % mod;
		y >>= 1;
	}
	return ans;
}
void prep(int n)
{
	int i;
	fac[0] = 1;
	for(i = 1; i <= n; i++)
		fac[i] = (ll)fac[i - 1] * i % mod;
	inv[n] = qpow(fac[n], mod - 2);
	for(i = n; i >= 1; i--)
		inv[i - 1] = (ll)inv[i] * i % mod;
	for(i = 1; i <= n; i++)
		Inv[i] = (ll)inv[i] * fac[i - 1] % mod;
}
int C(int x, int y)
{
	return (x < y || y < 0) ? 0 : ((ll)fac[x] * inv[y] % mod * inv[x - y] % mod);
}
int a[N], b[N];

int main()
{
	int t, n, m, A, B, i, j, val, tot;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d%d%d%d%d", &n, &mod, b, &A, &B);
		prep(2 * n + 1);
		for(i = 0; i <= n; i++)
			cat[i] = (ll)C(2 * i, i) * Inv[i + 1] % mod;
		val = 0;
		for(i = 0; i < n; i++)
			val = (val + (ll)cat[i] * cat[n - i - 1]) % mod;
		for(i = 1; i <= 2 * n; i++)
		{
			ans[i] = val;
			if(i & 1)
				val = (val + (ll)(mod - cat[n - (i + 1) / 2]) * cat[i / 2]) % mod;
		}
		for(i = 1; i <= 2 * n; i++)
			b[i] = ((ll)b[i - 1] * A + B) % mod;
		for(i = 1; i <= 2 * n; i++)
			a[i] = (a[i - 1] + b[i] + 1) % mod;
		tot = 0;
		for(i = 1; i <= 2 * n; i++)
		{
			val = (ans[2 * n + 1 - i] + mod - ans[i]) % mod;
			tot = (tot + (ll)val * a[i]) % mod;
		}
		tot = (ll)tot * qpow(cat[n], mod - 2) % mod;
		printf("%d\n", tot);
	}
	return 0;
}