Кактус
Справи йдуть не дуже добре. Те, що мало бути розслаблюючим вечором з друзями, обернулося ще гірше: на вас напала ходяча реклама дешевого одеколону, а ваш безцінний аргентинський кактус — єдине, що вам дороге, — викинули з вікна.
Одразу після події — або, скажімо так, як тільки це було фізично можливо — ви побігли вниз по сходах оцінювати збитки. І ось він, ваш безцінний кактус, живий! Десь є подряпини, але все ж таки живий. Як це сталося? Впав на щось м'яке? Переповнений радістю, ви вирішуєте не шукати відповідей. Я казав, що справи йдуть погано? Забийте, все чудово — і час святкувати! Звісно ж, в основі цього торжества буде ваш зелений жалючий друг.
Для тих, хто менш знайомий з ботанікою, нагадаємо: кактус — це зв'язний граф, кожна вершина якого лежить не більше ніж в одному циклі. Щоб додати святкового настрою, ви вирішили розфарбувати кожну вершину свого кактуса одним з k кольорів. Тут ви хотіли б дати собі більшу свободу, але бажаєте дотримуватися золотого правила розфарбування кактусів: жодні дві сусідні вершини не повинні бути пофарбовані в один і той самий колір.
Одного фарбування здається недостатньо, тому ви вирішили, що після того, як кольори потьмяніють, будете перефарбовувати кактус знову і знову, кожного разу використовуючи інше фарбування. Але як довго ви зможете це продовжувати? Знаючи опис вашого кактуса і число k, підрахуйте кількість правильних k-розфарбувань вершин кактуса. Оскільки відповідь може бути дуже великою, достатньо обчислити її залишок по модулю 10^9 + 7.
Вхідні дані
Перша рядок містить кількість тестів z (1 ≤ z ≤ 50 000). Далі слідують описи тестів.
Перша рядок кожного тесту містить три цілих числа n, m і k (1 ≤ n ≤ 300 000, 0 ≤ m ≤ 400 000, 2 ≤ k ≤ 10^9) — кількість вершин і ребер кактуса та кількість кольорів.
Кожен з наступних m рядків містить два цілих числа u[i], v[i] (1 ≤ u[i] ≠ v[i] ≤ n), відповідних ребрам кактуса. Гарантується, що даний граф є кактусом і будь-які дві вершини з'єднані не більше ніж одним ребром.
Загальна кількість вершин і ребер у всіх тестах не перевищує 3 * 10^6 і 4 * 10^6 відповідно.
Вихідні дані
Для кожного тесту виведіть одне ціле число: кількість правильних розфарбувань вершин кактуса k кольорами по модулю 10^9 + 7.