← 返回题目列表

Codeforces · 1580/B

B. 数学课程

中文机器翻译题面 查看原题

令 $$$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$$$ 获得。

输入

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

4 3 2 10007

输出 #1

4

输入 #2

6 4 1 769626776

输出 #2

472

输入 #3

66 11 9 786747482

输出 #3

206331312

输入#4

99 30 18 650457567

输出#4

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$$$ 本身。