题目描述

景明喜欢在庭院中栽种不同品种的苗木，尤其钟爱形态各异的珍稀苗木。他打算在庭院的一排土地上种植这些苗木，共有 $n$ 个可供种植的位置，准备了 $m$ 株不同的珍稀苗木。由于珍稀苗木生长需要充足空间，任意两株苗木之间必须至少留有一个空位置，不能相邻种植。

景明想知道，按照这种要求把 $m$ 株苗木全部种下，一共有多少种合法的方案。一个方案合法需满足上述种植要求，且由于苗木品种不同，方案的差异体现在：要么选择种植的位置不同，要么从左到右的苗木品种顺序不同。

最终答案需要对参数 $p$ 取模。

输入格式

每个输入文件包含一组测试数据，一行四个整数依次为 $type,~n,~m,~p$。其中 $type$ 用于标识测试点类型，具体含义见数据范围说明。

输出格式

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

1 3 2 19260718

2

提示

样例输入输出 1 解释

有 2 株珍稀苗木、3 个种植位置，苗木编号为 1、2，位置编号为 1、2、3，合法方案如下：

数据规模与约定

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

特殊性质 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$ 可辅助判断子任务编号