Во время своего приключения Перси со своими друзьями, Аннабет и Гроувером, столкнулся с Эридой — богиней хаоса и раздора. Оказалось, что в современном мире у нее меньше власти, и теперь, спустя столько времени она предпочитает хаосу и раздору что-то более мирное, например, здоровое соперничество и состязания в играх.
Правда это не означает, что компании друзей будет очень просто с ней договориться, и выяснить, что она может знать про украденные молнии Зевса. В обмен на информацию они должны сыграть с ней в ее любимую игру. По правилам игры игроки по очереди бросают $$$k$$$-гранные игральные кубики и выписывают последовательность выпавших на них чисел $$$a_i$$$ (нумерация с $$$1$$$), пока последовательность не станет размера $$$n$$$ ($$$n$$$ — нечетное).
Обозначим за $$$c$$$ центральный индекс последовательности, то есть $$$\frac{n+1}{2}$$$. Ребята побеждают, только если последовательность удовлетворяет следующим трем критериям:
В любом другом случае побеждает Эрида. Стоит обратить внимание, что любимые пары чисел Эриды — упорядоченные, то есть если Эриде нравится пара чисел $$$(x_i, y_i)$$$, не факт, что ей нравится $$$(y_i, x_i)$$$.
Перси заинтересовался, с какой вероятностью они смогут победить Эриду в этой игре, если каждое значение кубика выпадает равновероятно. Для этого необходимо посчитать общее количество последовательностей чисел от $$$1$$$ до $$$k$$$ длины $$$n$$$, удовлетворяющих описанным условиям. Помогите Перси посчитать это количество по модулю $$$10^9 + 7$$$, так как оно может быть слишком большим.
В первой строке ввода даны три целых числа $$$n$$$, $$$k$$$ и $$$m$$$ — необходимое количество бросков кубика (длина последовательности), количество граней кубика и количество любимых пар чисел Эриды ($$$1 \le n \le 53$$$; $$$n$$$ — нечетное; $$$2 \le k \le 10$$$; $$$0 \le m \le 16$$$). Гарантируется, что $$$(k - 1)^{n-1} \le 10^{36}$$$.
В $$$i$$$-й из следующих $$$m$$$ строк дана пара чисел $$$x_i$$$ и $$$y_i$$$ — $$$i$$$-я из любимых пар чисел Эриды ($$$1 \le x_i, y_i \le k$$$). Гарантируется, что все пары различны.
Выведите единственное целое число — количество последовательностей длины $$$n$$$, удовлетворяющих всем условиям.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Во всех группах, кроме группы 8, выполняется $$$(k - 1)^{n-1} \le 10^{30}$$$, а также все $$$m$$$ пар любимых чисел сгенерированы равновероятно.
Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
0 | – | примеры из условия | полная | |
1 | 9 | $$$m = 0$$$ | первая ошибка | |
2 | 12 | $$$m \le 1$$$ | 1 | первая ошибка |
3 | 15 | $$$m \le 2$$$ | 0 – 2 | первая ошибка |
4 | 9 | $$$m = k$$$, $$$x_i = y_i$$$ для всех $$$i$$$ | первая ошибка | |
5 | 11 | $$$n \le 25$$$, $$$(k-1)^{n-1} \le 2 \cdot 10^5$$$ | 0 | первая ошибка |
6 | 13 | $$$n \le 25$$$ | 0, 5 | первая ошибка |
7 | 9 | $$$x_i = y_i$$$ для всех $$$i$$$ | 4 | первая ошибка |
8 | 22 | $$$m \ge 10$$$ | 0 – 7 | первая ошибка |
3 6 16 6
25
5 8 11 2
49
7 5 21 22 1
254