Красивые раскраски 2047
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан неориентированный планарный граф на $$$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$$$ баллов. Балл за задачу равен сумме баллов по всем тестовым случаям.

Пример

Входные данные
1
7 9 4
1 2
2 3
3 4
4 5
3 6
5 6
3 5
6 7
7 4
Выходные данные
1080

Примечание

Планарный граф — граф, который можно изобразить на плоскости без пересечений рёбер не по вершинам.

В тесте из условия задан следующий граф: