#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tii;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define eb emplace_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)

const int N = 100007;
const int mod = 1000000007;

ull k1, k2;

ull xorShift128Plus() {
	ull k3 = k1, k4 = k2;
	k1 = k4;
	k3 ^= k3 << 23;
	k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
	return k2 + k4;
}

inline int fpow(int x, int t = mod - 2) {
	int ret = 1; 
	for (; t; t >>= 1, x = 1ll * x * x % mod)
		if (t & 1) ret = 1ll * ret * x % mod;
	return ret;
}

struct matrix {
	int n, m;
	vector<vector<int>> a;
	matrix(int n = 1, int m = 1) : n(n), m(m) {
		a.assign(n + 1, vector<int>(m + 1, 0));
	}
	inline int Det() {
		bool fl = 0;
		rep(i, 1, n) rep(j, 1, m) if (a[i][j] < 0) a[i][j] += mod;
		rep(i, 1, m) {
			int nw = i;
			rep(j, i, n) if (a[j][i]) {nw = j; break;}
			if (a[nw][i] == 0) return 0;
			if (nw != i) {swap(a[nw], a[i]); fl ^= 1;}
			int inv = fpow(a[i][i]);
			rep(j, i + 1, n) if (a[j][i]) {
				ll cof = mod - 1ll * inv * a[j][i] % mod;
				rep(k, i, n) a[j][k] = (a[j][k] + cof * a[i][k]) % mod;
			}
		}
		ll res = 1;
		rep(i, 1, n) res = res * a[i][i] % mod;
		return fl ? (mod - res) % mod : res;
	}
};

int f[N], tr[N];

int find(int x) {
	return x == f[x] ? x : (f[x] = find(f[x]));
}

bool vis[N];

vector<int> e[N];

vector<tuple<ull, int, int>> E;

inline void work() {
	E.clear();
	int n, m;
	cin >> n >> m >> k1 >> k2;
	rep(i, 1, n) f[i] = i;
	int mstcnt = 1;
	rep(i, 1, m) {
		int u = xorShift128Plus() % n + 1;
		int v = xorShift128Plus() % n + 1;
		ull w = xorShift128Plus();
		E.eb(w, u, v);
	}
	sort(all(E));
	int sum = 0, edgcnt = 0, ptr = 0;
	while (ptr < m) {
		ull nww = get<0>(E[ptr]);
		vector<pii> nwE;
		vector<int> nodes;
		while (ptr < m) {
			auto [w, u, v] = E[ptr];
			if (w != nww) break;
			if (find(u) != find(v)) {
				u = find(u);
				v = find(v);
				vis[u] = vis[v] = false;
				e[u].clear();
				e[v].clear();
				nwE.eb(u, v);
			}
			++ptr;
		}
		if (nwE.empty()) continue;
		for (auto [u, v] : nwE) {e[u].eb(v); e[v].eb(u);}
		// matrix tree
		auto calc = [&](int u) {
			vector<int> tmps;
			queue<int> q;
			q.push(u); vis[u] = true;
			while (!q.empty()) {
				u = q.front(); q.pop(); tmps.eb(u);
				for (auto v : e[u]) if (!vis[v]) {
					vis[v] = true; q.push(v);
				}
			}
			sort(all(tmps));
			int tmpn = tmps.size() - 1;
			rep(i, 0, tmpn) tr[tmps[i]] = i;
			matrix A(tmpn, tmpn);
			for (auto x : tmps) {
				A.a[tr[x]][tr[x]] = e[x].size();
				for (auto y : e[x]) --A.a[tr[x]][tr[y]];
			}
			mstcnt = 1ll * mstcnt * A.Det() % mod;
		};
		for (auto [u, v] : nwE) if (!vis[u]) calc(u);
		for (auto [u, v] : nwE) 
			if (find(u) != find(v)) {
				f[find(u)] = find(v);
				++edgcnt;
				sum = (sum + nww) % mod;
			}
	}
	if (edgcnt < n - 1) {puts("0"); return;}
	printf("%lld\n", 1ll * sum * mstcnt % mod);
}

int main() {
	int t; cin >> t;
	while(t--) work();
	return 0;
}