У Дореми есть \(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]\). Выходные данные
Выведите одно целое число — количество различных массивов \(a\), которые могут получиться как итог данной игры по модулю \(p\).
Примечание
В первом примере \(n=4\), в числе прочих могут получиться следующие массивы \(a\): \([4,2,3]\), \([1,4]\). Однако массив \(a\) не может быть равен \([1]\) или \([1,4,3]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 100000007
|
16
|
|
2
|
1145 141919831
|
105242108
|