Кактус
Кактус
Сразу скажу: дела идут не очень хорошо. То, что должно было стать расслабляющим вечером с друзьями, обернулось еще хуже: на Вас напала ходячая реклама дешевого одеколона, а Ваш бесценный аргентинский кактус - единственное, что вам дорого, - выкинули из окна.
Сразу после события - или, скажем так, как только это было физически возможно - Вы побежали вниз по лестнице оценивать убытки. И вот он, твой бесценный кактус, жив! Кое-где есть царапины, но тем не менее живой. Как это произошло? Упал на что-то мягкое? Переполненный радостью, Вы решаете не искать ответов. Я говорил, что дела идут плохо? Забей, все отлично - и пора праздновать! Конечно же, в основе этого торжества будет Ваш зеленый жалящий друг.
Для тех, кто менее знаком с ботаникой, мы напомним: кактус - это связный граф, каждая вершина которого лежит не более чем в одном цикле. Чтобы добавить праздничного настроения, Вы решаете раскрасить каждую вершину своего кактуса одним из k цветов. Здесь Вы хотели бы дать себе большую свободу, но желаете придерживаться золотого правила раскраски кактусов: никакие две соседние вершины не должны быть окрашены в один и тот же цвет.
Одного окрашивания кажется недостаточно, поэтому Вы решили, что после того, как цвета потускнеют, будете перекрашивать кактус снова и снова, каждый раз используя другую покраску. Но как долго вы сможете это продолжать? Зная описание вашего кактуса и число k, подсчитайте количество правильных k-раскрасок вершин кактуса. Поскольку ответ может быть очень большим, достаточно вычислить его остаток по модулю 109
+ 7.
Входные данные
Первая строка содержит количество тестов z (1 ≤ z ≤ 50 000). Далее следуют описания тестов.
Первая строка каждого теста содержит три целых числа n, m и k (1 ≤ n ≤ 300 000, 0 ≤ m ≤ 400 000, 2 ≤ k ≤ 109
) - количество вершин и ребер кактуса и количество цветов.
Каждая из следующих m строк содержит два целых числа ui
, vi
(1 ≤ ui
≠ vi
≤ n), соответствующих ребрам кактуса. Гарантируется, что данный граф является кактусом и любые две вершины соединены не более чем одним ребром.
Общее количество вершин и ребер во всех тестах не превышает 3 * 106
и 4 * 106
соответственно.
Выходные данные
Для каждого теста выведите одно целое число: количество правильных раскрасок вершин кактуса k цветами по модулю 109
+ 7.
2 2 1 100 1 2 6 7 3 1 2 2 3 3 1 4 5 5 6 6 4 1 4
9900 24