CF1580B.Mathematics Curriculum

Let $c_1, c_2, \ldots, c_n$ be a permutation of integers $1, 2, \ldots, n$. Consider all subsegments of this permutation containing an integer $x$. Given an integer $m$, we call the integer $x$ good if there are exactly $m$ different values of maximum on these subsegments.

Cirno is studying mathematics, and the teacher asks her to count the number of permutations of length $n$ with exactly $k$ good numbers.

Unfortunately, Cirno isn't good at mathematics, and she can't answer this question. Therefore, she asks you for help.

Since the answer may be very big, you only need to tell her the number of permutations modulo $p$.

A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

A sequence $a$ is a subsegment of a sequence $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

设 $c_1, c_2, \ldots, c_n$ 是整数 $1, 2, \ldots, n$ 的一个排列。考虑该排列中所有包含整数 $x$ 的子段（连续子数组）。给定整数 $m$，若在这些子段中，最大值恰好有 $m$ 个不同的取值，则称整数 $x$ 是“好的”。

琪露诺正在学习数学，老师让她计算长度为 $n$ 且恰好有 $k$ 个“好”的数的排列个数。

不幸的是，琪露诺不擅长数学，无法回答这个问题。因此，她向你求助。

由于答案可能非常大，你只需输出答案对 $p$ 取模的结果。

一个排列是由 $1$ 到 $n$ 中 $n$ 个互不相同的整数组成的数组，顺序任意。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数组中 $2$ 出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中出现了 $4$）。

若序列 $a$ 可通过从序列 $b$ 的开头删除若干（可能为零或全部）元素、并从结尾删除若干（可能为零或全部）元素而得到，则称 $a$ 是 $b$ 的一个子段。

The first line contains four integers $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$).

第一行包含四个整数 $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$）。

Output the number of permutations modulo $p$.

输出排列数对 $p$ 取模的结果。

In the first test case, there are four permutations: $[1, 3, 2, 4]$, $[2, 3, 1, 4]$, $[4, 1, 3, 2]$ and $[4, 2, 3, 1]$.

Take permutation $[1, 3, 2, 4]$ as an example:

For number $1$, all subsegments containing it are: $[1]$, $[1, 3]$, $[1, 3, 2]$ and $[1, 3, 2, 4]$, and there're three different maxima $1$, $3$ and $4$.

Similarly, for number $3$, there're two different maxima $3$ and $4$. For number $2$, there're three different maxima $2$, $3$ and $4$. And for number $4$, there're only one, that is $4$ itself.

在第一个测试用例中，共有四个排列：$[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$。