配点 : $900$ 点

問題文

整数 $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]$ の最長増加部分列の長さに等しい。
• $1$ から $N$ までの各 $i$ について、$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$ で割った余りを出力せよ。

3 2 686926217

1

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

4 3 354817471

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

5 2 829412599

1

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

5 3 975576997

23

69 42 925171057

801835311