#include <bits/stdc++.h>

using namespace std;


struct edge{
    int u,v;
    unsigned long long w;
    bool operator <(const edge& other) const {
        return w < other.w;
    }
} e[100001];
const unsigned long long P = 1e9+7;
unsigned long long k1 , k2;
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;
}
int n, m, u [100001] , v [100001];
unsigned long long w [100001];
void gen () {
scanf ("%d%d%llu%llu", &n, &m, &k1 , &k2);
for ( int i = 1; i <= m; ++i) {
u[i] = xorShift128Plus () % n + 1;
v[i] = xorShift128Plus () % n + 1;
w[i] = xorShift128Plus () ;
}
}

int fa[100001];
int get_fa(int x){
    if (fa[x] == x) return x;
    return fa[x] = get_fa(fa[x]);
}
bool merge(int x,int y){
    int fx = get_fa(x);
    int fy = get_fa(y);
    if (fx == fy) return false;
    fa[fx] = fy; 
    return true;
}


void solve(){
    gen();
    for (int i = 1; i <= n; ++i){
        fa[i] = i;
    }
    for (int i = 1; i <= m; ++i){
        e[i].u = u[i];
        e[i].v = v[i];
        e[i].w = w[i];
    }
    sort(e+1,e+m+1);
    unsigned long long ans = 0;
    int cnt=0;
    for (int i = 1; i <= m; ++i){
        // if (i <= 10) {
        //     cout << e[i].u << " " << e[i].v << " " << e[i].w << "\n";
        // }
        if (merge(e[i].u,e[i].v)){
            cnt++;
            ans += e[i].w%P;
            ans %= P;
        }
    }
    if(cnt==n-1)printf("%llu\n",ans);
    else printf("0\n");
}
int main(){
    // ios_base::sync_with_stdio(0);
    // cin.tie(0);
    int T;
    // cin >> T;
    scanf("%d",&T);
    while(T--){
        solve();
    }

}