← 返回题目列表

AtCoder · agc055_c

C. 奇怪的LIS

中文机器翻译题面 查看原题

分数: 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