首先，我必須坦白：事情進展得並不順利。原本應該是與朋友共度的輕鬆夜晚卻急轉直下：你遭到了一名噴著廉價古龍水的路人襲擊，而你最珍視的寶貝——那盆無價的阿根廷仙人掌——被扔出了窗外。

事發之後——或者說，在身體允許的最快時間內——你跑下樓梯去評估損失。就在那裡，你的無價仙人掌，活著！雖然身上有些許擦傷，但它依然活著。這是怎麼發生的？它掉在柔軟的東西上了嗎？欣喜若狂的你決定不去深究原因。我剛才說事情進展不順利嗎？撤回前言，一切都很棒——現在是慶祝的時候了！當然，這場慶祝活動的核心將會是你那位綠色的刺刺朋友。

對於不太熟悉植物學的人，這裡提供一個複習：仙人掌圖（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