分数: 650 点
问题陈述
给你整数 A, B,和 M.
有多少种排列 P = (P_1, \dots, P_{AB-1}) of (1, 2, \ldots, AB - 1) 满足以下所有条件?求计数模数 M.
- 的最长递增子序列的长度 P is A.
- 的最长递减子序列的长度 P is B.
- 存在一个整数 n 这样附加 n + 0.5 到年底 P 不改变最长递增子序列和最长递减子序列的长度。
约束
- 所有输入值均为整数。
- 2 \leq A, B
- AB \leq 120
- 10^8 \leq M \leq 10^9
- M 是素数。
输入
输入由标准输入按以下格式给出:
A B M
输出
打印满足条件的排列数,模 M.
示例输入 1
3 2 998244353
示例输出 1
10
例如, P = (2, 4, 5, 1, 3) 满足条件。这可以通过以下方式确认:
- 的最长递增子序列的长度 P is 3.
- 的最长递减子序列的长度 P is 2.
- 对于 n = 4,最长递增和递减子序列的长度 (2, 4, 5, 1, 3, 4.5) 是 3 和 2。
有 10 的排列 (1, 2, 3, 4, 5) 满足条件。
示例输入 2
10 12 924844033
示例输出 2
623378361
打印计数模数 M.