Сразу скажу: дела идут не очень хорошо. То, что должно было стать расслабляющим вечером с друзьями, обернулось еще хуже: на Вас напала ходячая реклама дешевого одеколона, а Ваш бесценный аргентинский кактус - единственное, что вам дорого, - выкинули из окна.

Сразу после события - или, скажем так, как только это было физически возможно - Вы побежали вниз по лестнице оценивать убытки. И вот он, твой бесценный кактус, жив! Кое-где есть царапины, но тем не менее живой. Как это произошло? Упал на что-то мягкое? Переполненный радостью, Вы решаете не искать ответов. Я говорил, что дела идут плохо? Забей, все отлично - и пора праздновать! Конечно же, в основе этого торжества будет Ваш зеленый жалящий друг.

Для тех, кто менее знаком с ботаникой, мы напомним: кактус - это связный граф, каждая вершина которого лежит не более чем в одном цикле. Чтобы добавить праздничного настроения, Вы решаете раскрасить каждую вершину своего кактуса одним из 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.