大家好！我是你们的老朋友 Rikka。欢迎来到徐州。这是第一道题，关于最小生成树（MST）。我向大家保证，这对大多数人来说应该是最简单的一道题。
最小生成树（Minimum Spanning Tree, MST）是一个带权无向图的边子集，它构成一棵树，连接所有顶点，且总边权之和最小，同时不包含任何环。
在本题中，Rikka 希望你计算给定图中所有 MST 的总边权之和。显然，这等于一棵 MST 的总边权与不同 MST 总数的乘积。注意，如果两棵生成树的边集不同，则它们是不同的。此外，不连通的图可能没有 MST，此时不同 MST 的数量为零。
为了减小输入规模，Rikka 通过一个带有给定随机种子（由两个整数 $k_1$ 和 $k_2$ 表示）的随机数生成器提供了一个带权无向图。假设图中的顶点数和边数分别为 $n$ 和 $m$，以下 C++ 代码展示了如何生成该图，并将第 $i$ 条连接顶点 $u[i]$ 和 $v[i]$ 且权值为 $w[i]$ 的边存储在相应的数组中。你可以直接在提交的代码中使用这段代码。
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();
}
}此外，为了减小输出规模，你的代码应输出答案对 $(10^9 + 7)$ 取模后的结果。
如果你已经知道如何处理这些，那就开始你的表演，忽略剩下的题目描述吧。
为了确保每个人都知道如何解决这个问题，Rikka 在这里为大家提供一个有效的练习，它可以解决这个问题并帮助大家获得 Accepted！
首先你需要了解的是 Kirchhoff 矩阵树定理。给定一个具有 $n$ 个顶点且无自环的无向图 $G$，其拉普拉斯矩阵 $L_{n \times n}$ 定义为 $(D - A)$，其中 $D$ 是度数矩阵，$A$ 是图的邻接矩阵。更准确地说，在矩阵 $L$ 中，元素 $l_{i,j}$ ($i \neq j$) 等于 $-m$，其中 $m$ 是第 $i$ 个顶点和第 $j$ 个顶点之间的边数，$L_{i,i}$ 等于第 $i$ 个顶点的度数。接下来，通过从 $L$ 中删除任意一行和任意一列来构造矩阵 $L^*$，例如，删除第 1 行和第 1 列。Kirchhoff 矩阵树定理表明，生成树的数量恰好是 $L^*$ 的行列式，这可以在多项式时间内计算出来。
现在让我解释一种计算 MST 数量的算法。该算法将用于 MST 的 Kruskal 算法分解为一系列块，每个块由一系列关于在多重图（多重图是指两个顶点之间可能有多条边相连的图）中添加相同权值边的操作组成，其顶点是之前操作块所构建的连通分量。
准确地说，我们将第 $i$ 个操作块完成后构建的多重图标记为 $G_i$。不失一般性，考虑没有操作的第 0 块，令 $G_0$ 为一个具有 $n$ 个孤立顶点的空图。第 $i$ 个操作块将 $G_{i-1}$ 中通过该块中的边相连的顶点压缩为一个单一顶点。结果正是图 $G_i$。
如果你非常了解 Kruskal 算法的基本原理，你可能会发现 MST 的数量是每个定义权值的块中图的每个连通分量的生成树数量的乘积。实际上，基于 Kruskal 算法中的贪心策略，对于特定的权值，其边数在所有 MST 中是固定的。最后，Kirchhoff 矩阵树定理可以帮助你计算图的生成树数量。
输入格式
输入包含多个测试用例，第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。
对于每个测试用例，唯一的一行包含四个整数 $n$ ($1 \le n \le 10^5$)，$m$ ($m = 10^5$)，$k_1$ 和 $k_2$ ($10^8 \le k_1, k_2 \le 10^{12}$)，其中 $k_1$ 和 $k_2$ 除样例外均为随机选择。
输出格式
对于每个测试用例，输出一行，包含一个数字，即答案对 $(10^9 + 7)$ 取模后的结果。
样例
输入格式 1
1 2 100000 123456789 987654321
输出格式 1
575673759
说明
由于生成器代码仅提供 C++ 版本，Rikka 强烈建议大家使用 C 或 C++ 来解决此问题，而不是其他编程语言。