問題文

整数 $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$ で割った余りを出力してください。

制約

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

---

入力

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

$N$ $M$ $Q$

出力

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

---

入力例 1

3 2 686926217

出力例 1

1

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

---

入力例 2

4 3 354817471

出力例 2

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

---

入力例 3

5 2 829412599

出力例 3

1

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

---

入力例 4

5 3 975576997

出力例 4

23

---

入力例 5

69 42 925171057

出力例 5

801835311