Перси Джексон и встреча с Эридой
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Во время своего приключения Перси со своими друзьями, Аннабет и Гроувером, столкнулся с Эридой — богиней хаоса и раздора. Оказалось, что в современном мире у нее меньше власти, и теперь, спустя столько времени она предпочитает хаосу и раздору что-то более мирное, например, здоровое соперничество и состязания в играх.

Правда это не означает, что компании друзей будет очень просто с ней договориться, и выяснить, что она может знать про украденные молнии Зевса. В обмен на информацию они должны сыграть с ней в ее любимую игру. По правилам игры игроки по очереди бросают $$$k$$$-гранные игральные кубики и выписывают последовательность выпавших на них чисел $$$a_i$$$ (нумерация с $$$1$$$), пока последовательность не станет размера $$$n$$$ ($$$n$$$ — нечетное).

Обозначим за $$$c$$$ центральный индекс последовательности, то есть $$$\frac{n+1}{2}$$$. Ребята побеждают, только если последовательность удовлетворяет следующим трем критериям:

  1. число $$$k$$$ выпало только один раз, и находится ровно в середине последовательности; более формально — $$$a_c = k$$$ и $$$a_i \ne k$$$ для всех $$$i \ne c$$$;
  2. числа с одной стороны от центра на отличающихся в два раза расстояниях от него, одинаковы; то есть для любого $$$d$$$ от $$$-\left\lfloor\frac{c-1}{2}\right\rfloor$$$ до $$$-1$$$ и от $$$1$$$ до $$$\left\lfloor\frac{c-1}{2}\right\rfloor$$$ верно $$$a_{c+d} = a_{c+2d}$$$;
  3. каждая из $$$m$$$ любимых пар чисел Эриды $$$(x_i, y_i)$$$ встречается в последовательности подряд не более одного раза раз.

В любом другом случае побеждает Эрида. Стоит обратить внимание, что любимые пары чисел Эриды — упорядоченные, то есть если Эриде нравится пара чисел $$$(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примеры из условияполная
19$$$m = 0$$$первая ошибка
212$$$m \le 1$$$1первая ошибка
315$$$m \le 2$$$0 – 2первая ошибка
49$$$m = k$$$, $$$x_i = y_i$$$ для всех $$$i$$$первая ошибка
511$$$n \le 25$$$, $$$(k-1)^{n-1} \le 2 \cdot 10^5$$$0первая ошибка
613$$$n \le 25$$$0, 5первая ошибка
79$$$x_i = y_i$$$ для всех $$$i$$$4первая ошибка
822$$$m \ge 10$$$0 – 7первая ошибка

Примеры

Входные данные
3 6 1
6 6
Выходные данные
25
Входные данные
5 8 1
1 2
Выходные данные
49
Входные данные
7 5 2
1 2
2 1
Выходные данные
254