盒子里有 n 个球,颜色仅黑白两种,但初始时黑白球的具体数量(初始状态)未知。
共进行 m 次操作,每次操作流程为:
- 从盒子中取出一个球
- 放入黑白球各一个
- 再取出一个球
经过 m 次操作后,取出的 2×m 个球会形成一个序列。需计算所有可能的初始状态下,本质不同的序列总数,并对 p 取模后输出。
- 两个序列本质不同的定义:存在至少一个位置,对应位置的球颜色不同。
- 初始状态指盒子中最初黑球和白球的数量组合。
输入格式
一行三个整数,依次为 n、m、p,分别表示初始球总数、操作次数、取模参数。
输出格式
一行一个整数,表示所有初始状态下本质不同的序列总数对 p 取模的结果。
样例:
Input#1
1 2 114514
Output#1
8
Input#2
30 30 1919
Output#2
1299
Input#3
1000 1000 998244353
Output#3
708964705