Красивые раскраски 2047 - 2

В этой задаче на проверку необходимо сдать текстовый файл с ответом. Входные данные вы можете скачать, нажав на кнопку с изображением стрелки справа-сверху рядом с кнопкой «Объявления жюри».

Дан неориентированный планарный граф на n n вершинах и целое положительное число k k . Назовем раскраску графа красивой, если никакие две соседние его вершины не покрашены в один цвет (для лучшего понимания рекомендуем обратиться к разделу "Примечание"). Найдите количество красивых раскрасок графа в k k цветов.

Формат ввода

В первой строке ввода находится единственное целое число t t  — количество тестовых случаев, которые вам будет необходимо обработать ( 1 t 100 ) (1 \leq t \leq 100) .

Первая строка каждого тестового случая содержит целые числа n n , m m и k k  — количество вершин и рёбер графа, а также количество доступных цветов. Ограничения на параметры смотри в разделе «Система оценивания». Обратите внимание, что с ростом n n значение k k в тестах убывает.

Следующие m m строк содержат по два целых числа u , v u, v , задающих рёбра графа.

Формат вывода

Для каждого тестового случая выведите единственное число — количество красивых раскрасок графа по модулю 1 0 9 + 7 10^9+7 .

Система оценивания

Оценка за эту задачу — 50 баллов, тестирование проводится оффлайн (баллы за задачу будут известны после окончания тура).

Каждый тестовый случай оценивается независимо. Правильный ответ оценивается в 2 2 балла. Неправильный ответ оценивается в 0 0 баллов. Балл за задачу равен сумме баллов по всем тестовым случаям.

Ниже приведены значения n , m , k n, m, k в каждом из тестовых случаев.

тест n n m m k k тест n n m m k k тест n n m m k k
1 24 30 4 11 20 25 5 21 11 13 7
2 22 27 4 12 24 30 4 22 12 15 7
3 20 25 5 13 26 32 4 23 13 16 7
4 20 25 6 14 28 35 4 24 14 17 7
5 19 23 5 15 30 37 4 25 15 18 7
6 18 22 7 16 12 15 5
7 18 22 8 17 13 16 5
8 16 20 4 18 14 17 5
9 16 20 5 19 15 18 5
10 15 18 4 20 10 12 7

Примечания

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

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

image