Мы называем массив $$$a$$$ длины $$$n$$$ изысканным, если для каждого $$$1 < i \le n$$$ верно, что $$$a_i = a_{i-1} + 1$$$.

Назовем $$$f(p)$$$, применяемую к перестановке$$$^\dagger$$$ длины $$$n$$$, как минимальное количество подмассивов, на которые можно разбить перестановку так, чтобы каждый из них был изысканным. Например, $$$f([1,2,3]) = 1$$$, а $$$f([3,1,2]) = 2$$$ и $$$f([3,2,1]) = 3$$$.

Учитывая $$$n$$$ и перестановку $$$p$$$ длины $$$n$$$, мы определяем перестановку $$$p'$$$ длины $$$n$$$ как $$$k$$$-специальную тогда и только тогда, когда:

• $$$p'$$$ лексикографически меньше$$$^\ddagger$$$, чем $$$p$$$, и
• $$$f(p') = k$$$.

Ваша задача — посчитать для каждого $$$1 \le k \le n$$$ количество $$$k$$$-специальных перестановок по модулю $$$m$$$.

$$$^\dagger$$$ Перестановка — это массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — это перестановка, но $$$[1,2,2]$$$ — не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве есть $$$4$$$).

$$$^\ddagger$$$ Перестановка $$$a$$$ длины $$$n$$$ лексикографически меньше перестановки $$$b$$$ длины $$$n$$$ тогда и только тогда, когда выполняется следующее: в первой позиции, где $$$a$$$ и $$$b$$$ различаются, перестановка $$$a$$$ имеет меньший элемент, чем соответствующий элемент в $$$b$$$.