时空限制

3S/1024M

题目描述

jiangly 正在某 OJ 上做题，OJ 上共有 $n$ 道题目。

jiangly 打算提交每一道题各一次，每道题的评测结果可能是 AC，也可能是 WA。因此，jiangly 的初始评测状态共有 $2^n$ 种可能的情况。

OJ 管理员 Bob 不希望 jiangly 顺利 AC。对于某一种特定的初始评测状态，Bob 可以选择至多 $k$ 道题（可以选择已经是 WA 的题目，也可以不选任何一个题目），强制将它们的评测状态变为 WA。

我们称 jiangly 的最终评测状态为“听取蛙声一片”，当且仅当最终的状态中存在连续 $m$ 个（或更多）题目的评测状态为 WA。

现在你需要求出：在所有 $2^n$ 种初始评测状态下，Bob 能够使最终状态变为“听取蛙声一片”的方案数的总和。

换句话说，我们需要计算满足以下条件的二元组 $(S, T)$ 的数量：

1. $S$ 是一个长度为 $n$ 的初始状态序列（由 AC/WA 组成）。
2. $T$ 是一个题目下标的集合，满足 $0 \le |T| \le k$。
3. 将 $S$ 中下标在 $T$ 中的题目的状态全部强制变为 WA 后，序列中存在连续至少 $m$ 个 WA。

由于答案可能很大，请输出答案对 $P$ 取模的结果。

格式

输入格式

一行四个整数 $n, m, k, P$，分别表示题目数量、连续 WA 的目标长度、Bob 最多能修改的题目数以及模数。

输出格式

一个整数，表示方案数总和模 $P$ 的结果。

样例

样例输入 #1

3 2 2 998244353

样例输出 #1

37

样例解释 #1

$n=3, m=2, k=2$。我们需要连续 $2$ 个 WA。

共有 $2^3=8$ 种初始情况。对于每种情况，Bob 可以选择的下标集合 $T$（$|T| \le 2$）如下：

1. AC, AC, AC：需改出连续 2 个 WA。
   • 合法集合 $T$: $\{1,2\}, \{2,3\}$。共 $2$ 种。
2. AC, AC, WA：
   • 合法集合 $T$: $\{2\} , \{1,2\} ,\{2,3\}$ 。共 $3$ 种。
3. AC, WA, AC：
   • 合法集合 $T$: $\{1\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}$。共 $5$ 种。
4. WA, AC, AC：
   • 合法集合 $T$: $\{2\}, \{1,2\}, \{2,3\}$。共 $3$ 种。
5. WA, AC, WA：
   • 合法集合 $T$: $\{2\}, \{1,2\}, \{2,3\}$。共 $3$ 种。
6. 其余 $3$ 种情况：
   • 初始已经满足“听取蛙声一片”。
   • Bob 可以选择任意大小 $\le 2$ 的集合 $T$，该集合共有 $7$ 种。
   • $3$ 种状态共 $3 \times 7 = 21$ 种。

故总和为：$2 + 3 + 5 + 3 + 3 + 21 = 37$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n \le$
$1$	$20$	$10$
$2$	$40$	$400$
$3$	$40$	$5000$

对于 $100\%$ 的数据，满足 $1 \le m, k \le n \le 5000$，$10^8 \le P \le 10^9$。

注意：$P$ 不一定是质数。