数学课程

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

设 $c_1,c_2,\ldots,c_n$ 是 $1,2,\ldots,n$ 的一个排列。考虑这个排列中所有包含整数 $x$ 的连续子数组。给定整数 $m$，如果这些连续子数组的最大值恰好有 $m$ 种不同取值，就称整数 $x$ 是好数。

求长度为 $n$、恰好含有 $k$ 个好数的排列数量。答案对 $p$ 取模。

输入格式

一行包含四个整数 $n,m,k,p$。

输出格式

输出满足条件的排列数量对 $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\le n\le100$，$1\le m,k\le n$，$1\le p\le10^9$。