You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

星川之下皆萤火尘埃，
我独行在人潮你天真而待。
相遇若是借丹青着色，
青原上 绯樱如海。

——银临《青原樱》(Cover 人衣大人)

题目描述

扶苏是一个非常喜欢边听古风鸽边写数学题的人，因此这道题其实是个五三原题。

扶苏希望重现青原上樱花盛开的景色，于是他准备了很多互不相同樱花树幼苗，准备种成一行。

这一行中，一共有 $n$ 个位置可以种下樱花，而扶苏准备了 $m$ 支幼苗。由于樱花盛放时对左右空间需求非常大，所以樱花不能紧挨着种植，也就是任意两支幼苗之间必须至少存在一个不种花的空位置。

按照这种方式种花并不难，但是令扶苏感到好奇的是一共有多少合法的方案让他把这 $m$ 支幼苗都种下去。一个方案是合法的当且仅当他满足上一段中叙述的要求。如果我们将花按照 $1,2,3,\dots,m$ 编号，两种方案不同当且仅当被选择种花的位置不同或从左向右数花的编号序列不同。

为了避免输出过大，答案对一个参数 $p$ 取模。

输入格式

每个输入文件中有且仅有一组测试数据。

测试数据只有一行四个整数，依次代表 $type,~n,~m,~p$，其中 $type$ 是一个帮助你判断测试点类型的参数，会在数据范围中说明。

输出格式

输出一行一个整数，代表答案对 $p$ 取模的结果。

1 3 2 19260718

2

提示

样例输入输出 1 解释

一共有 $2$ 个樱花幼苗， $3$ 个种花的位置，如果给幼苗编号为 $1,~2$，位置编号为 $1,~2,~3$，那么两种方案分别如下：

位置	$1$	$2$	$3$
方案 1	幼苗 $1$	空	幼苗 $2$
方案 2	幼苗 $2$		幼苗 $1$

---

数据规模与约定

本题采用多测试点捆绑测试，共有 6 个子任务。

子任务编号	$n \leq$	$m \leq$	$type=$	特殊性质	子任务分值
1	$1$		$0$	特殊性质 1	$5$
2	$20$		$1$		$15$
3	$400$	$200$	$2$	无	$20$
4	$2000$		$3$
5	$2000000$	$1000000$	$4$	特殊性质 2
6			$5$	无

特殊性质 1：保证对应测试点的实际方案数(在取模前)不超过 $10^6$

特殊性质 2：保证 $p$ 是一个质数。

对于 $100\%$ 的数据，保证：

• $1 \leq n \leq 2 \times 10^6$。
• $1 \leq m \leq 10^6$。
• $1 \leq p \leq 10^9$。
• $1 \leq m \leq \lceil\frac{n}{2} \rceil$。

---

提示

• 请使用合适的数据类型来进行运算，避免溢出。
• 参数 $type$ 可以帮助你快速的判断子任务编号。