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