#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
constexpr int M=1e5+5,mod=1e9+7;
vector<tuple<ull,int,int>>edge;
int T,n,m,cnt,f[M];ull k1,k2,ans;
ull rnd(){
    ull k3=k1,k4=k2;
    k1=k4;k3^=k3<<23;
    k2=k3^k4^(k3>>17)^(k4>>26);
    return k2+k4;
}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
void solve(){ edge.clear();ans=cnt=0;
    scanf("%d%d%llu%llu",&n,&m,&k1,&k2);
    for (int i=1;i<=m;i++){
        int u=rnd()%n+1,v=rnd()%n+1;
        edge.emplace_back(rnd(),u,v);
    }
    sort(edge.begin(),edge.end());
    for (int i=1;i<=n;i++) f[i]=i;
    for (auto [z,x,y]:edge){
        int fx=find(x),fy=find(y);
        if (fx==fy) continue;
        f[fx]=fy;ans+=z%mod;cnt++;
    }
    printf("%llu\n",cnt==n-1?ans%mod:0);
}
int main(){scanf("%d",&T);while (T--) solve();return 0;}