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