B. Курс математики
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пусть $$$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$$$ удалением нескольких (возможно, ни одного или всех) элементов из начала и нескольких (возможно, ни одного или всех) элементов из конца.

Входные данные

Единственная строка входных данных содержит четыре целых числа $$$n, m, k, p$$$ ($$$1 \le n \le 100, 1 \le m \le n, 1 \le k \le n, 1 \le p \le 10^9$$$).

Выходные данные

Выведите количество перестановок по модулю $$$p$$$.

Примеры
Входные данные
4 3 2 10007
Выходные данные
4
Входные данные
6 4 1 769626776
Выходные данные
472
Входные данные
66 11 9 786747482
Выходные данные
206331312
Входные данные
99 30 18 650457567
Выходные данные
77365367
Примечание

В первом тестовом случае четырьмя перестановками являются $$$[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$$$.