SP8331 SSTRCITS - Sister cities

与其邻国“反乌托邦”不同，乌托邦相信经济发展。为了推动经济进步，乌托邦政府决定选择一些城市对作为姐妹城市，并加强这些城市对之间的贸易关系。 乌托邦有 $N$ 座城市，编号为 $1$ 到 $N$。这些城市中有些由双向道路连接，乌托邦的道路总数为 $R$。现有的道路网络已经被高效地设计，使得没有多余的道路。换句话说，从任意一座城市到另一座城市，只有一条路径，而且不会重复使用任何道路。当选择一对城市作为姐妹城市时，政府希望两者之间存在一条直接的道路。此外，每座城市最多只能选择一个姐妹城市。 给定乌托邦的道路网络，计算在这些约束条件下选择 $K$ 对姐妹城市的方法数。由于答案可能非常大，输出结果时请取模 $100000007$。 例如，假设乌托邦有 $6$ 座城市。以下城市对之间有直接道路：$(1,2)$、$(2,3)$、$(2,4)$、$(4,5)$、$(4,6)$。注意，在任意两座城市之间，都只有唯一一种不重复使用同一条道路的旅行方式。如果政府想选择两对姐妹城市，有以下四种方式：$\{(1,2),(4,5)\}$、$\{(3,2),(4,5)\}$、$\{(1,2),(4,6)\}$、$\{(3,2),(4,6)\}$。

第一行是整数 $T$，表示测试用例的数量。 每个测试用例由一个包含三个空格分隔整数的行开始，分别是 $N$（城市数量，$N < 400$）、$R$（道路数量，$R < 10000$）和 $K$（需要选择的姐妹城市对数，$K < 400$）。接下来的 $R$ 行中，每行表示一条道路，包含两个不同的空格分隔整数 $N_1$ 和 $N_2$，表示 $N_1$ 和 $N_2$ 之间有一条双向道路。可以确保道路网络符合题目描述中的特性。

对于每个测试用例，输出一种满足题目条件的选择 $K$ 对姐妹城市的方法数，并对结果取模 $100000007$。

- $1 \le T \le 10$ - $1 \le N < 400$ - $1 \le R < 10000$ - $1 \le K < 400$ **本翻译由 AI 自动生成**