| Codeforces Global Round 24 |
|---|
| Закончено |
У Дореми есть $$$n+1$$$ колышек. $$$n$$$ красных колышков расставлены в вершины правильного $$$n$$$-угольника и пронумерованы от $$$1$$$ до $$$n$$$ против часовой стрелки. Также есть синий колышек несколько меньшего диаметра по центру многоугольника. Вокруг красных колышков натянута резинка.
Дореми сегодня очень скучно, поэтому она решила сыграть в игру. Изначально у нее есть пустой массив $$$a$$$. До тех пор, пока резинка не коснется синего колышка, она будет повторять следующую операцию:
- выбрать $$$i$$$ ($$$1 \leq i \leq n$$$) такое, что красный колышек номер $$$i$$$ еще не был убран;
- убрать красный колышек номер $$$i$$$;
- добавить $$$i$$$ в конец массива $$$a$$$.
Дореми интересно, сколько различных массивов $$$a$$$ может получиться как итог данного процесса. Так как ответ может быть большим, выведите его по модулю $$$p$$$. Гарантируется, что $$$p$$$ — простое число.
Игра с $$$n=9$$$ и $$$a=[7,5,2,8,3,9,4]$$$, а также игра с $$$n=8$$$ и $$$a=[3,4,7,1,8,5,2]$$$. Первая строка содержит два целых числа $$$n$$$ и $$$p$$$ ($$$3 \leq n \leq 5000$$$, $$$10^8 \le p \le 10^9$$$) — количество красных колышков и модуль соответственно.
Гарантируется, что $$$p$$$ — простое число.
Выведите одно целое число — количество различных массивов $$$a$$$, которые могут получиться как итог данной игры по модулю $$$p$$$.
4 100000007
16
1145 141919831
105242108
В первом примере $$$n=4$$$, в числе прочих могут получиться следующие массивы $$$a$$$: $$$[4,2,3]$$$, $$$[1,4]$$$. Однако массив $$$a$$$ не может быть равен $$$[1]$$$ или $$$[1,4,3]$$$.
