F. Палиндромный гамильтонов путь
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан простой неориентированный граф с $$$n$$$ вершинами, $$$n$$$ четно. Вы планируете написать одну букву на каждой вершине. Каждая буква должна быть одной из первых $$$k$$$ букв латинского алфавита.

Путь в графе называется гамильтоновым, если он посещает каждую вершину ровно один раз. Строка называется палиндромной, если она читается одинаково слева направо и справа налево. Путь в графе называется палиндромным, если при выписывании букв с вершин в порядке пути получается палиндромная строка.

Строка длины $$$n$$$ хорошая, если:

  • каждая буква — это одна из первых $$$k$$$ латинского алфавита;
  • если написать $$$i$$$-ю букву строки на $$$i$$$-й вершине графа, то в графе будет существовать палиндромный гамильтонов путь.

Обратите внимание, что путь не обязан проходить по вершинам в порядке $$$1, 2, \dots, n$$$.

Посчитайте количество хороших строк.

Входные данные

В первой строке записаны три целых числа $$$n$$$, $$$m$$$ and $$$k$$$ ($$$2 \le n \le 12$$$; $$$n$$$ четно; $$$0 \le m \le \frac{n \cdot (n-1)}{2}$$$; $$$1 \le k \le 12$$$) — количество вершин в графе, количество ребер в графе и количество первых букв алфавита, которые можно использовать.

В каждой из следующих $$$m$$$ строк записаны по два целых числа $$$v$$$ и $$$u$$$ ($$$1 \le v, u \le n$$$; $$$v \neq u$$$) — ребра графа. Граф не содержит кратных ребер и петель.

Выходные данные

Выведите одно целое число — количество хороших строк.

Примеры
Входные данные
4 3 3
1 2
2 3
3 4
Выходные данные
9
Входные данные
4 6 3
1 2
1 3
1 4
2 3
2 4
3 4
Выходные данные
21
Входные данные
12 19 12
1 3
2 6
3 6
3 7
4 8
8 5
8 7
9 4
5 9
10 1
10 4
10 6
9 10
11 1
5 11
7 11
12 2
12 5
12 11
Выходные данные
456165084