题目描述

一座花园的灯架形成了一张连通无向图。为了方便维护，这张图是一棵“仙人掌”：每个顶点最多位于一个简单环上，并且任意两点之间至多有一条边。

园艺师准备给每个顶点安装一种颜色的灯泡。共有 k 种颜色可选，要求任意一条边连接的两个顶点颜色不同。

请计算一共有多少种合法染色方案。答案可能很大，只需要输出它对 10^9 + 7 取模后的结果。

输入格式

第一行包含一个整数 z，表示测试用例数量。

每个测试用例的第一行包含三个整数 n, m, k，分别表示顶点数、边数和颜色数。

接下来 m 行，每行包含两个整数 u_i, v_i，表示一条连接 u_i 与 v_i 的无向边。

保证输入图是连通仙人掌图，每个顶点最多位于一个简单环上，并且没有重边。

输出格式

对每个测试用例，输出一行一个整数，表示合法 k 染色方案数对 10^9 + 7 取模的结果。

数据范围

• 1 <= z <= 50000
• 1 <= n <= 300000
• 0 <= m <= 400000
• 2 <= k <= 10^9
• 所有测试用例的 n 之和不超过 3 * 10^6
• 所有测试用例的 m 之和不超过 4 * 10^6

样例

2
2 1 100
1 2
6 7 3
1 2
2 3
3 1
4 5
5 6
6 4
1 4

9900
24