Пусть \(c_1, c_2, \ldots, c_n\) — перестановка чисел \(1, 2, \ldots, n\). Рассмотрим все подотрезки этой перестановки, содержащие число \(x\). Для фиксированного числа \(m\) скажем, что \(x\) хорошее, если среди максимумов на данных отрезках встречается ровно \(m\) различных значений.
Cirno изучает математику, и учитель просит ее найти количество перестановок длины \(n\) с ровно \(k\) хорошими числами.
К сожалению, Cirno не сильна в математике и не может ответить на этот вопрос. Поэтому она просит вас о помощи.
Поскольку ответ может быть очень большим, вам нужно только сообщить ей количество перестановок по модулю \(p\).
Перестановкой является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Последовательность \(a\) является подотрезком \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) элементов из начала и нескольких (возможно, ни одного или всех) элементов из конца.
Выходные данные
Выведите количество перестановок по модулю \(p\).
Примечание
В первом тестовом случае четырьмя перестановками являются \([1, 3, 2, 4]\), \([2, 3, 1, 4]\), \([4, 1, 3, 2]\) и \([4, 2, 3, 1]\).
Возьмем перестановку \([1, 3, 2, 4]\) в качестве примера:
Для числа \(1\) все подотрезки, содержащие его, являются: \([1]\), \([1, 3]\), \([1, 3, 2]\) и \([1, 3, 2, 4]\), и есть три разных максимума \(1\), \(3\) и \(4\).
Аналогично, для числа \(3\) существуют два разных максимума \(3\) и \(4\). Для числа \(2\) существует три разных максимума \(2\), \(3\) и \(4\). А для числа \(4\) есть только один, то есть сам по себе \(4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3 2 10007
|
4
|
|
2
|
6 4 1 769626776
|
472
|
|
3
|
66 11 9 786747482
|
206331312
|
|
4
|
99 30 18 650457567
|
77365367
|