题目描述

给定整数 $N,\ M$。请计算满足以下条件的长度为 $N$ 的序列 $A=[A_1,\ A_2,\ \ldots,\ A_N]$ 的个数。

• $2 \leq A_i \leq M$（$1 \leq i \leq N$）。
• 存在一个 $1$ 到 $N$ 的整数的排列 $P=[P_1,P_2,\ldots,P_N]$，使得对于 $1$ 到 $N$ 的每个 $i$，$A_i$ 等于序列 $[P\_1,\ P\_2,\ \ldots,\ P\_{i-1},\ P\_{i+1},\ \ldots,\ P\_N]$ 的最长上升子序列的长度。

由于答案可能非常大，请输出其对素数 $Q$ 取模的结果。

输入格式

输入为一行，格式如下：

$N$ $M$ $Q$

输出格式

输出答案对 $Q$ 取模后的结果。

样例 1

输入

3 2 686926217

输出

1

样例 2

输入

4 3 354817471

输出

9

样例 3

输入

5 2 829412599

输出

1

样例 4

输入

5 3 975576997

输出

23

样例 5

输入

69 42 925171057

输出

801835311

说明/提示

限制条件

• $3 \leq N \leq 5000$
• $2 \leq M \leq N-1$
• $10^8 \leq Q \leq 10^9$
• $Q$ 是素数。

样例解释 1

满足条件的序列只有 $[2, 2, 2]$。此时存在排列 $[1, 2, 3]$ 满足题意。

样例解释 2

满足条件的序列有以下 $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

满足条件的序列只有 $[2, 2, 2, 2, 2]$。

由 ChatGPT 4.1 翻译