H1. Игра ИИ (простая версия)
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Это упрощенная версия задачи. Разница между легкой и сложной версиями заключается в ограничении на $$$k$$$ и ограничении по времени. Кроме того, в этой версии задачи вам нужно вычислить ответ только при $$$n=k$$$. Вы можете делать взломы только в том случае, если обе версии задачи решены.

Cirno играет в военный симулятор с $$$n$$$ башнями (пронумерованными от $$$1$$$ до $$$n$$$) и $$$n$$$ ботами (пронумерованными от $$$1$$$ до $$$n$$$). Первоначально $$$i$$$-я башня занята $$$i$$$-м ботом для всех $$$1 \le i \le n$$$.

Перед игрой Cirno сначала выбирает перестановку $$$p = [p_1, p_2, \ldots, p_n]$$$ длины $$$n$$$ (перестановкой длины $$$n$$$ называется массив длины $$$n$$$, где каждое целое число между $$$1$$$ и $$$n$$$ встречаются ровно один раз). После этого она может выбрать последовательность $$$a = [a_1, a_2, \ldots, a_n]$$$ ($$$1 \le a_i \le n$$$ и $$$a_i \ne i$$$ для всех $$$1 \le i \le n$$$ ).

В игре есть $$$n$$$ раундов-атак. В $$$i$$$-м раунде, если $$$p_i$$$-й бот все еще находится в игре, он начнет свою атаку, в результате чего $$$a_{p_i}$$$-я башня будет занята $$$p_i$$$-м ботом; бот, который ранее занимал $$$a_{p_i}$$$-ю башню, больше не будет ее занимать. Если $$$p_i$$$-го бота нет в игре, в этом раунде ничего не произойдет.

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

В конце игры Cirno запишет результат в виде последовательности $$$b = [b_1, b_2, \ldots, b_n]$$$, где $$$b_i$$$ — номер бота, занимающего $$$i$$$-ю башня в конце игры.

Однако, как мастер математики, она хочет, чтобы вы решили следующую задачу на счет вместо того, чтобы играть в игры:

Подсчитайте количество различных пар последовательностей $$$a$$$ и $$$b$$$, которые могут получиться из всех возможных выборов последовательности $$$a$$$ и перестановки $$$p$$$.

Так как это число может быть большим, выведите его по модулю $$$M$$$.

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

Единственная строка содержит два натуральных числа $$$k$$$ и $$$M$$$ ($$$1\le k\le 5000$$$, $$$2\le M\le 10^9$$$ ). Гарантируется, что $$$2^{18}$$$ — делитель $$$M-1$$$, а $$$M$$$ — простое число.

Вам нужно вывести ответ для $$$n=k$$$.

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

Выведите одно целое число — количество различных пар последовательностей для $$$n=k$$$ по модулю $$$M$$$.

Примеры
Входные данные
1 998244353
Выходные данные
0
Входные данные
2 998244353
Выходные данные
2
Входные данные
3 998244353
Выходные данные
24
Входные данные
8 998244353
Выходные данные
123391016
Примечание

Для $$$n=1$$$ допустимой последовательности $$$a$$$ не существует. Мы рассматриваем ответ как $$$0$$$.

При $$$n=2$$$ возможен только один массив $$$a$$$: $$$[2, 1]$$$.

  • Для массива $$$a$$$ равного $$$[2, 1]$$$ и перестановки $$$p$$$ равной $$$[1, 2]$$$, последовательность $$$b$$$ будет $$$[1, 1]$$$ после всех раундов. Детали для каждого раунда:
    • В первом раунде первый бот начнет атаку и успешно захватит башню $$$2$$$. После этого раунда второй бот будет уничтожен и покинет игру, так как все его башни заняты другими ботами.
    • Во втором раунде второго бота нет в игре.
  • Для массива $$$a$$$ равного $$$[2, 1]$$$ и перестановки $$$p$$$ равной $$$[2, 1]$$$, последовательность $$$b$$$ будет $$$[2, 2]$$$ после всех раундов. Детали для каждого раунда:
    • В первом раунде второй бот начнет атаку и успешно захватит башню $$$1$$$. После этого раунда первый бот будет уничтожен и покинет игру, так как все его башни заняты другими ботами.
    • Во втором раунде первого бота нет в игре.

Таким образом, количество различных пар последовательностей $$$(a,b)$$$ равно $$$2$$$ ($$$[2, 1]$$$, $$$[1, 1]$$$ и $$$[2, 1]$$$, $$$[2, 2]$$$) при $$$n=2$$$.