Дан неориентированный планарный граф на $$$n$$$ вершинах и целое положительное число $$$k$$$. Назовем раскраску графа красивой, если никакие две соседние его вершины не покрашены в один цвет (для лучшего понимания рекомендуем обратиться к разделу "Примечание"). Найдите количество красивых раскрасок графа в $$$k$$$ цветов.
В первой строке ввода находится единственное целое число $$$t$$$ — количество тестовых случаев, которые вам будет необходимо обработать $$$(1 \leq t \leq 100)$$$.
Первая строка каждого тестового случая содержит целые числа $$$n$$$, $$$m$$$ и $$$k$$$ — количество вершин и рёбер графа, а также количество доступных цветов $$$(1 \leq n \leq 30, 1 \leq m \leq 40, 1 \leq k \leq 11)$$$. Обратите внимание, что с ростом $$$n$$$ значение $$$k$$$ в тестах убывает.
Следующие $$$m$$$ строк содержат по два целых числа $$$u, v$$$, задающих рёбра графа.
Для каждого тестового случая выведите единственное число — количество красивых раскрасок графа по модулю $$$10^9+7$$$.
Каждый тестовый случай оценивается независимо. Правильный ответ оценивается в $$$2$$$ балла. Неправильный ответ оценивается в $$$0$$$ баллов. Балл за задачу равен сумме баллов по всем тестовым случаям.
Оценка за эту задачу — 50 баллов, тестирование проводится оффлайн (баллы за задачу будут известны после окончания тура).
Планарный граф — граф, который можно изобразить на плоскости без пересечений рёбер не по вершинам.
В тесте из условия задан следующий граф: