题目描述

大家好！我是你们的老朋友果粒橙(@)。这是一个关于最小生成树（MST）的问题。我向大家保证，这绝对是对学过MST的人来说最简单的一道题。

最小生成树（或最小权重生成树）是一个连通的无向权值图的边子集，它构成了一棵包含所有顶点的树，且所有边的权值之和最小。

在本题中，你需计算一个给定图中所有不同 MST 的总权值之和。注意：如果两棵生成树的边集不同，则认为它们是不同的。此外，如果一个图是不连通的，则它没有 MST，总权值之和为 $0$。

为了减小输入文件的大小，我提供了一个带有给定随机种子（由两个整数 $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)$ 取模后的结果。

如果你已经知道如何处理这个问题，现在就可以开始你的表演，略过以下所有的说明。

为了确保每个人都知道如何解决这个问题，我在这里提供了一个有效的练习方案，可以帮助大家获得 AC：

首先，你需要了解 基尔霍夫矩阵树定理。给定一个拥有 $n$ 个顶点且无自环的无向图 $G$，其拉普拉斯矩阵 $L_{n \times n}$ 定义为 $D - A$，其中 $D$ 是度数矩阵，$A$ 是图的邻接矩阵。更精确地说，在矩阵 $L$ 中，条目 $l_{i,j} \ (i \neq j)$ 等于顶点 $i$ 和顶点 $j$ 之间边数的负值，而 $l_{i,i}$ 等于顶点 $i$ 的度数。接着，通过删除 $L$ 的任意一行和一列（例如删除第一行和第一列）构造一个矩阵 $L^*$。基尔霍夫矩阵树定理指出，生成树的数量恰好等于 $L^*$ 的行列式，这可以在多项式时间内计算出来。

现在让我解释一个计算 MST 数量的算法。该算法将 Kruskal 算法求 MST 的过程分解为一系列块，每个块由向多重图中添加相同权值的一系列边组成。

准确地说，我们将添加完第 $i$ 块操作后的多重图标记为 $G_i$。不失一般性，考虑第 $0$ 块（没有任何操作），令 $G_0$ 为一个拥有 $n$ 个孤立顶点的空图。第 $i$ 块操作将 $G_{i-1}$ 中的顶点“挤压”成单个顶点，这些顶点由该块中权值相同的边连接。结果正是图 $G_i$。

如果你非常熟悉 Kruskal 算法的基本原理，你会发现 MST 的数量是图中每个“权值定义块”对应的分量中生成树数量的乘积。实际上，对于某个特定权值，其在所有 MST 中出现的边数是固定的。最后，基尔霍夫矩阵树定理可以帮助你计算图的生成树数量。

输入格式

输入包含多组测试用例。第一行包含一个整数 $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
5 100000 123456789 987654321

570537339

提示

由于随机数生成器代码仅提供了 C++ 版本，我强烈建议选手使用 C/C++ 而非其他编程语言来解决此问题，当然如果你能1:1翻译为其他语言，那请自便。

备注

题源：2018徐州A题