AT_agc055_c.[AGC055C] Weird LIS

给定整数 $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$ 取模后的结果。

限制条件

• $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 翻译