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