分数: 900 点
问题陈述
给你整数 N 和 M。 查找数组的数量 A=[A_1, A_2, \ldots, A_N] 长度 N 使得以下条件成立:
- 2 \le A_i \le M (1 \leq i \leq N)
- 存在一个排列 P=[P_1,P_2,\ldots,P_N] 的整数来自 1 to N 具有以下属性:
- 对于每个 i 来自 1 to N, A_i 等于序列的最长递增子序列的长度 [P_1, P_2, \ldots, P_{i-1}, P_{i+1}, \ldots, P_{N-1}, P_N].
由于这个数字可能非常大,因此输出它对素数取模 Q.
约束
- 3 \le N \le 5000.
- 2 \le M \le N-1.
- 10^8 \le Q \le 10^9
- Q 是质数。
输入
输入由标准输入按以下格式给出:
N M Q
输出
打印答案模数 Q.
示例输入 1
3 2 686926217
示例输出 1
1
唯一的这样的数组是 [2, 2, 2],存在一个排列 [1, 2, 3].
示例输入 2
4 3 354817471
示例输出 2
9
有 9 这样的数组: [2, 2, 2, 2], [2, 2, 2, 3], [2, 2, 3, 2], [2, 2, 3, 3], [2, 3, 2, 2], [2, 3, 3, 2], [3, 2, 2, 2], [3, 3, 2, 2], [3, 3, 3, 3].
示例输入 3
5 2 829412599
示例输出 3
1
唯一的这样的数组是 [2, 2, 2, 2, 2].
示例输入 4
5 3 975576997
示例输出 4
23
示例输入 5
69 42 925171057
示例输出 5
801835311