题目描述

整数 $N,\ M$ が与えられます。次の条件を満たす長さ $N$ の列 $A=[A_1,\ A_2,\ \ldots,\ A_N]$ の個数を求めてください。

• $2\ \le\ A_i\ \le\ 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-1},\ P_N] $ の最長増加部分列の長さに等しい。

この個数は非常に大きい可能性があるため、これを素数 $Q$ で割った余りを出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $Q$

输出格式

答えを $Q$ で割った余りを出力せよ。

题目大意

记 $f(p)$ 表示排列 $p$ 的最长上升子序列长度。

记 $P_i$ 表示排列 $p$ 去掉第 $i$ 个数的序列。求有多少长为 $N$，值域为 $[2,M]$ 的序列 $a$ 使得：存在一个排列 $p$，$\forall i$ 有 $f(P_i)=a_i$。

答案对素数 $Q$ 取膜。

3 2 686926217

1

4 3 354817471

9

5 2 829412599

1

5 3 975576997

23

69 42 925171057

801835311

提示

制約

• $3\ \le\ N\ \le\ 5000$
• $2\ \le\ M\ \le\ N-1$
• $10^8\ \le\ Q\ \le\ 10^9$
• $Q$ は素数である。

Sample Explanation 1

このような列は $[2,\ 2,\ 2]$ のみです。ここで $[1,\ 2,\ 3]$ という順列が存在して性質を満たします。

Sample Explanation 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]$。

Sample Explanation 3

このような列は $[2,\ 2,\ 2,\ 2,\ 2]$ のみです。