[AdditionalFile4054.zip](file://AdditionalFile4054.zip?type=additional_file)

#4054. 「GDKOI-S 2024」鸡

标签: 传统 | 时间限制: 3000 ms | 内存限制: 512 MiB |

题目描述

对于一个非负整数序列 $a$，定义它对应的独立集序列 $f(a)$：

• 假设将 $a_i$ 改为 $0$，此时选出若干个两两不相邻的数使得它们的和最大，则 $f(a)_i$ 表示和的最大值。

现在给定 $n, m$，求有多少个长度为 $b$ 的非负整数序列 $b$ 满足以下条件：

• 存在至少一个长度为 $n$，值域为 $[0, m]$ 的非负整数序列 $a$ 使得 $f(a) = b$。

答案对给定的质数 $MOD$ 取模。

输入格式

共一行，三个数，表示 $n, m, MOD$。

输出格式

共一行，一个数，表示答案。

样例 1

输入

3 1 1000000007

输出

6

样例 2

输入

4 2 1000000007

输出

47

样例 3

输入

20 24 1000000007

输出

141754844

样例 4

输入

123 234 1000000009

输出

141754844

样例 5

输入

1234 2345 1004535809

输出

576196526

数据范围与提示

本题使用子任务捆绑测试。

对于 $100\%$ 的数据，$1 \leq n, m \leq 3 \times 10^3$，$n \geq 2$，$10^9 < MOD < 1.01 \times 10^9$，$MOD$ 为质数。

• Subtask 1（$10\%$）：$n, m \leq 5$。
• Subtask 2（$15\%$）：$n \leq 300$，$m = 1$。
• Subtask 3（$25\%$）：$n \leq 300$，$m\leq 5$。
• Subtask 4（$20\%$）：$n, m \leq 50$。
• Subtask 5（$15\%$）：$n, m \leq 300$。
• Subtask 6（$15\%$）：无特殊限制。