题目描述

大家好！我是你们的老朋友 Rikka。欢迎来到徐州。这是第一题，一道关于最小生成树（MST）的题目。我向你们保证，对大多数人来说这应该是 最简单的问题。

最小生成树，或称最小权重生成树，是从边带权无向图中选出的一个边子集，它们构成一棵树，能够在没有任何环的情况下以最小的总边权连接所有顶点。

在本题中，Rikka 想让你计算给定图的所有最小生成树的总边权之和，显然，这等于单棵最小生成树的总边权乘以不同最小生成树的总数。注意，若两棵生成树的边集不同，则认为它们是不同的生成树。此外，一个不连通的图可能没有生成树，此时不同生成树的数量为零。

为了减小输入规模，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！

首先你需要知道的是基尔霍夫矩阵树定理。给定一个包含 $n$ 个顶点且不含自环的无向图 $G$，其拉普拉斯矩阵 $L_{n \times n}$ 定义为 $(D - A)$，其中 $D$ 是度数矩阵，$A$ 是图的邻接矩阵。更确切地说，矩阵 $L$ 中的元素 $l_{i, j}$（$i \ne j$）等于 $-m$，其中 $m$ 是第 $i$ 个顶点与第 $j$ 个顶点之间的边数；而 $L_{i, i}$ 等于第 $i$ 个顶点的度数。接下来，从 $L$ 中删去任意一行和任意一列（例如删去第 $1$ 行和第 $1$ 列）构造矩阵 $L^{\ast}$。基尔霍夫矩阵树定理指出，生成树的数量恰好是 $L^{\ast}$ 的行列式，这可以在多项式时间内计算出来。

现在让我解释一个计算最小生成树数量的算法。该算法将 Kruskal 最小生成树算法拆分成一系列块，每个块由一系列操作组成，这些操作将相同权重的边加入一个多重图（多重图是一个顶点间可能存在多条边的图），该多重图的顶点是在前一个操作块中已经构建好的连通分量。

确切地说，设在第 $i$ 个操作块之后构建的多重图为 $G_i$。不失一般性，考虑第 $0$ 个块（无任何操作），并令 $G_0$ 为具有 $n$ 个孤立顶点的空图。第 $i$ 个操作块将 $G_{i-1}$ 中由该块内的边相连的顶点收缩成一个单一顶点，结果即为图 $G_i$。

如果你对 Kruskal 算法的基本原理了然于胸，你可能会发现，最小生成树的数量就是每个块定义权重的图中，每个连通分量的生成树数量的乘积。实际上，基于 Kruskal 算法中的贪心选择策略，在所有最小生成树中，某个特定权重的边的数量是固定的。最后，基尔霍夫矩阵树定理能帮助你计算这些图的生成树数量。

输入格式

输入包含多组测试数据，第一行是一个整数 $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
2 100000 123456789 987654321

575673759

提示

由于生成器代码仅提供 C++ 版本，Rikka 强烈建议你们使用 C 或 C++ 来解决本题，而非其他编程语言。

翻译由 DeepSeek V4 Pro 完成