首先，让我们开诚布公地说：情况不太妙。原本应该是一个与朋友共度的轻松夜晚，却变得糟糕透顶：你被一个廉价古龙水的移动广告牌袭击了，而你视若珍宝的无价阿根廷仙人掌——你唯一珍视的东西——被扔出了窗外。

事发之后——或者说，在身体条件允许的情况下——你立刻跑下楼梯去评估损失。就在那里，你的无价仙人掌，还活着！虽然身上有些擦伤，但依然活着。这是怎么发生的？它落在了柔软的东西上吗？欣喜若狂的你决定不去深究原因。我说过情况不太妙吗？划掉那句话，一切都很棒——现在是庆祝的时候了！当然，这场庆祝的核心将是你这位绿色的带刺朋友。

那些不太熟悉植物学的人现在可以复习一下：仙人掌图（cactus）是一个连通图，其中每个顶点至多属于一个环。为了增加节日气氛，你决定用 $k$ 种颜色中的一种来为仙人掌的每个顶点着色。你希望在这里给自己留出很大的自由度，但你确实想遵守仙人掌着色的黄金法则：没有两个相邻的顶点被分配相同的颜色。

一种着色方案似乎还不够，所以你决定在颜色褪去后，一次又一次地重新为仙人掌着色，每次都使用不同的着色方案。但你能坚持多久呢？给定仙人掌的描述和颜色数量 $k$，计算仙人掌顶点的正确 $k$-着色方案数。由于答案可能非常大，你只需要计算其对 $10^9 + 7$ 取模后的余数。

输入格式

第一行包含测试用例的数量 $z$ ($1 \le z \le 50\,000$)。接下来是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$ ($1 \le n \le 300\,000, 0 \le m \le 400\,000, 2 \le k \le 10^9$)，分别表示仙人掌的顶点数、边数和颜色数。

接下来的 $m$ 行，每行包含两个整数 $u_i, v_i$ ($1 \le u_i \neq v_i \le n$)，对应仙人掌的边。保证给定的图是一个仙人掌，且任意两个顶点之间至多有一条边。

所有测试用例中顶点数和边数的总和分别不超过 $3 \cdot 10^6$ 和 $4 \cdot 10^6$。

输出格式

对于每个测试用例，输出一个整数：用 $k$ 种颜色对仙人掌顶点进行正确着色的方案数，结果对 $10^9 + 7$ 取模。

样例

输入 1

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

输出 1

9900
24