Задан простой неориентированный граф с \(n\) вершинами, \(n\) четно. Вы планируете написать одну букву на каждой вершине. Каждая буква должна быть одной из первых \(k\) букв латинского алфавита.
Путь в графе называется гамильтоновым, если он посещает каждую вершину ровно один раз. Строка называется палиндромной, если она читается одинаково слева направо и справа налево. Путь в графе называется палиндромным, если при выписывании букв с вершин в порядке пути получается палиндромная строка.
Строка длины \(n\) хорошая, если:
- каждая буква — это одна из первых \(k\) латинского алфавита;
- если написать \(i\)-ю букву строки на \(i\)-й вершине графа, то в графе будет существовать палиндромный гамильтонов путь.
Обратите внимание, что путь не обязан проходить по вершинам в порядке \(1, 2, \dots, n\).
Посчитайте количество хороших строк.