题目描述

给定整数 $N$ 和 $M$。找出长度为 $N$ 的数组 A=\[A_1, A_2, \\ldots, A_N\] 的数量，满足以下条件：

• $2 \\le A_i \\le M$ ($1 \\leq i \\leq N$)
• 存在一个排列 P=\[P_1,P_2,\\ldots,P_N\]，其中 $P$ 是从 $1$ 到 $N$ 的整数，满足以下属性：
  • 对于 $1 \\le i \\le 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