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

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

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