CF1580B Mathematics Curriculum

设 $c_1, c_2, \ldots, c_n$ 是 $1, 2, \ldots, n$ 的一个排列。考虑该排列中包含整数 $x$ 的所有子区间。给定一个整数 $m$，如果对于整数 $x$，在所有包含 $x$ 的子区间中，最大值出现了恰好 $m$ 种不同的取值，则称 $x$ 是“好数”。 琪露诺正在学习数学，老师要求她统计长度为 $n$ 的排列中恰好有 $k$ 个好数的排列数量。 由于答案可能非常大，你只需输出对 $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$ 取模的结果。

在第一个测试用例中，有四个排列：$[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$ 本身。 由 ChatGPT 4.1 翻译