Мы называем массив \(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\).
Примечание
В первом примере перестановки, лексикографически меньшие, чем \([1,3,4,2]\), следующие:
- \([1,2,3,4]\), \(f([1,2,3,4])=1\);
- \([1,2,4,3]\), \(f([1,2,4,3])=3\);
- \([1,3,2,4]\), \(f([1,3,2,4])=4\).
Таким образом, наш ответ \([1,0,1,1]\).
Во втором примере перестановки, лексикографически меньшие, чем \([3,2,1]\), следующие:
- \([1,2,3]\), \(f([1,2,3])=1\);
- \([1,3,2]\), \(f([1,3,2])=3\);
- \([2,1,3]\), \(f([2,1,3])=3\);
- \([2,3,1]\), \(f([2,3,1])=2\);
- \([3,1,2]\), \(f([3,1,2])=2\).
Таким образом, наш ответ равен \([1,2,2]\).