#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
//typedef long long ll;
unsigned long long k1 , k2;
//typedef pair<ll, ll> pii;
const ull M = 1000000007;
unsigned long long xorShift128Plus () 
{
	unsigned long long k3 = k1 , k4 = k2;
	k1 = k4;
	k3 ^= k3 << 23;
	k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26) ;
	return k2 + k4;
}
ull n, m, u , v, w;
struct edge
{
	ull w, x, y;	
	edge(){
		
	}
	edge(ull p, ull q, ull r)
	{
		w=p, x=q, y=r;
	}
};
//vector<pii> graph[100100];
vector<edge> edges;
ull  bcj[100100];
const ull INF = 0xffffffffffffffff;
ull  find(ull  x)
{
	if(bcj[x] == INF) return x;
	ull  tmp = find(bcj[x]);
	bcj[x] = tmp;
	return tmp;
}
bool trymerge(ull  x, ull  y)
{
	ull  p = find(x), q = find(y);
	if(p != q) 
	{
		bcj[q] = p;
		return 1;
	}
	return 0;
}
bool cmp(edge x, edge y)
{
	return x.w < y.w;
}
void gen () {
	scanf ("%llu%llu%llu%llu", &n, &m, &k1 , &k2);
//	for(ull i=0; i<n; i++) graph[i].clear();
	edges.clear();
	for ( ull i = 1; i <= m; ++i) 
	{
		u = xorShift128Plus () % n + 1;
		v = xorShift128Plus () % n + 1;
		w = xorShift128Plus () ;
//		cin >> u >> v >> w;
//		graph[u].push_back({v, w});
//		graph[v].push_back({u, w});
		edges.push_back(edge(w, u, v));
	}
}

int main()
{
	ull  z;
	cin >> z;
	while(z--)
	{
		gen();
		memset(bcj, 0xff, sizeof(ull ) * (n+5));
		sort(edges.begin(),edges.end(), cmp);
		ull comp = n;
		ull ans = 0;
		for(ull i=0; i<m; i++)
		{
			edge &cur = edges[i];
			if(trymerge(cur.x, cur.y))
			{
				ans = (ans + cur.w %M) % M;
				comp--;
			}
			if(comp == 1) break;
		}
		cout << ans << '\n';
	}
	
	return 0;
}