Дан неориентированный планарный граф на \(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\).
Планарный граф — граф, который можно изобразить на плоскости без пересечений рёбер не по вершинам.
В тесте из условия задан следующий граф:
| № | Входные данные | Выходные данные |
|
1
|
1
7 9 4
1 2
2 3
3 4
4 5
3 6
5 6
3 5
6 7
7 4
|
1080
|