Дан неориентированный планарный граф на $$$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)$$$.
Следующие $$$m$$$ строках содержат по два целых числа $$$u, v$$$, задающих рёбра графа.
Для каждого тестового случая выведите единственное число — количество красивых раскрасок графа по модулю $$$10^9+7$$$. Гарантируется, что до взятия по модулю ответ не превосходит $$$50\cdot 10^6$$$.
Оценка за эту задачу — 50 баллов, тестирование проводится онлайн (после тура баллы за задачу не изменятся).
Каждый тестовый случай оценивается независимо. Правильный ответ оценивается в $$$2$$$ балла. Неправильный ответ оценивается в $$$0$$$ баллов. Балл за задачу равен сумме баллов по всем тестовым случаям.
17 9 41 22 33 44 53 65 63 56 77 4
1080
Планарный граф — граф, который можно изобразить на плоскости без пересечений рёбер не по вершинам.
В тесте из условия задан следующий граф: