Кактус#11105

Кактус

1 секунда

128 мегабайтів

Дуже складна

Справи йдуть не надто добре. Те, що мало бути затишним вечором із друзями, стало ще гірше: на вас напала ходяча реклама дешевого одеколону, а ваш безцінний аргентинський кактус — єдине, що вам реально дороге, — викинули з вікна.

Відразу після цього — або, як тільки це стало можливо, — ви побігли вниз сходами оцінити збитки. І ось він — ваш безцінний кактус, живий! Є подряпини, але живий. Як так сталося? Впав на щось м’яке? Радіючи, ви вирішуєте не перейматись цим питанням. Казав, що справи йдуть погано? Забудьте, усе добре — час святкувати! Звісно, у центрі цього свята — ваш зелений колючий друг.

Для тих, хто мало знайомий із ботанікою, нагадуємо: кактус — це зв’язний граф, у якому кожна вершина належить не більш як одному циклу. Щоб додати святковості, ви вирішили розфарбувати кожну вершину свого кактуса одним із $k$ кольорів. Хотілося б більшої свободи, але діє правило розфарбування кактусів: сусідні вершини не мають бути пофарбовані в один і той самий колір.

Одного фарбування замало, тому ви вирішили, що коли кольори вигорять, будете перефарбовувати кактус знову й знову, кожного разу інакше. Та як часто це можна повторювати? Знаючи опис вашого кактуса і число $k$ , підрахуйте кількість правильних $k$ -розфарбувань вершин кактуса. Оскільки відповідь може бути дуже великою, достатньо обчислити її залишок за модулем $1 0^{9} + 7$ 10^9 + 7.

Вхідні дані

Перший рядок містить кількість тестів $z$ ( $1 \leq z \leq 50000$ 1 \leq z \leq 50\,000). Далі йдуть описи тестів.

Перший рядок кожного тесту містить три цілих числа $n$ , $m$ і $k$ ( $1 \leq n \leq 300000$ 1 \leq n \leq 300\,000, $0 \leq m \leq 400000$ 0 \leq m \leq 400\,000, $2 \leq k \leq 1 0^{9}$ 2 \leq k \leq 10^9) — кількість вершин і ребер кактуса та кількість кольорів.

Кожен з наступних $m$ рядків містить два цілих числа $u_{i}$ u_i, $v_{i}$ v_i ( $1 \leq u_{i} \neq = v_{i} \leq n$ 1 \leq u_i \neq v_i \leq n), відповідних ребрам кактуса. Гарантується, що цей граф — кактус, і будь-які дві вершини з'єднані не більш як одним ребром.

Загальна кількість вершин і ребер у всіх тестах не перевищує $3 \cdot 1 0^{6}$ 3 \cdot 10^6 і $4 \cdot 1 0^{6}$ 4 \cdot 10^6 відповідно.

Вихідні дані

Для кожного тесту виведіть одне ціле число: кількість правильних розфарбувань вершин кактуса $k$ кольорами за модулем $1 0^{9} + 7$ 10^9 + 7.

Приклади

Приклад 1