率直に言わせてもらうと、事態は芳しくありません。友人たちとリラックスした夜を過ごすはずが、安っぽい香水の歩く広告に襲われ、あなたの大切な宝物であるアルゼンチンサボテンが窓から投げ捨てられてしまったのです。

事件の直後、あるいは物理的に可能な限りすぐに、あなたは被害状況を確認するために階段を駆け下りました。するとそこには、あなたのサボテンが生きているではありませんか！あちこちに傷はありますが、それでも生きています。どうしてこんなことが起きたのでしょうか？何か柔らかいものの上に落ちたのでしょうか？喜びのあまり、あなたは答えを探すのをやめることにしました。事態は芳しくないと言いましたっけ？そんなことは忘れてください。すべては最高です。今こそ祝杯を挙げる時です！もちろん、この祝宴の中心には、あなたの緑色のトゲトゲした友人がいるはずです。

植物学にあまり詳しくない方のために補足すると、サボテン（cactus）とは、各頂点が最大で1つのサイクルにしか含まれない連結グラフのことです。お祝いの気分を盛り上げるために、あなたはサボテンのすべての頂点を $k$ 色のうちの1色で塗り分けることにしました。ここでは自由度を高くしたいところですが、サボテンの彩色における黄金律、すなわち「隣接する2つの頂点には同じ色を割り当ててはならない」というルールは守らなければなりません。

1通りの彩色では物足りないため、色が褪せるたびに、毎回異なる彩色方法でサボテンを塗り直すことにしました。しかし、いつまでこれを続けられるでしょうか？サボテンの構造と色数 $k$ が与えられたとき、サボテンの頂点の正しい $k$ 彩色の総数を求めてください。答えは非常に大きくなる可能性があるため、$10^9 + 7$ で割った余りを求めてください。

入力

入力の最初の行には、テストケースの数 $z$ ($1 \le z \le 50\,000$) が含まれます。続いて各テストケースの説明が続きます。

各テストケースの最初の行には、3つの整数 $n, m, k$ ($1 \le n \le 300\,000, 0 \le m \le 400\,000, 2 \le k \le 10^9$) が含まれます。これらはそれぞれ、サボテンの頂点数、辺数、および色数を表します。

続く $m$ 行には、サボテンの辺に対応する2つの整数 $u_i, v_i$ ($1 \le u_i \neq v_i \le n$) がそれぞれ含まれます。与えられたグラフはサボテンであり、どの2頂点間も最大で1本の辺で結ばれていることが保証されています。

すべてのテストケースにおける頂点数と辺数の合計は、それぞれ $3 \cdot 10^6$ および $4 \cdot 10^6$ を超えません。

出力

各テストケースについて、$k$ 色を用いたサボテンの正しい彩色の総数を $10^9 + 7$ で割った余りを1行に出力してください。

入出力例

入力 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