Problem Statement

You are given integers $N$ and $M$. Find the number of arrays A=\[A_1, A_2, \\ldots, A_N\] of length $N$ such that the following conditions hold:

• $2 \\le A_i \\le M$ ($1 \\leq i \\leq N$)
• There exists a permutation P=\[P_1,P_2,\\ldots,P_N\] of integers from $1$ to $N$ with the following property:
  • For every $i$ from $1$ to $N$, $A_i$ equals the length of the longest increasing subsequence of the sequence $\[P_1, P_2, \\ldots, P_{i-1}, P_{i+1}, \\ldots, P_{N-1}, P_N\]$.

As this number can be very large, output it modulo some prime $Q$.

Constraints

• $3 \\le N \\le 5000$.
• $2 \\le M \\le N-1$.
• $10^8 \\le Q \\le 10^9$
• $Q$ is a prime.

---

Input

Input is given from Standard Input in the following format:

$N$ $M$ $Q$

Output

Print the answer modulo $Q$.

---

Sample Input 1

3 2 686926217

Sample Output 1

1

The only such array is \[2, 2, 2\], for which exists a permutation \[1, 2, 3\].

---

Sample Input 2

4 3 354817471

Sample Output 2

9

There are $9$ such arrays: \[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 Input 3

5 2 829412599

Sample Output 3

1

The only such array is \[2, 2, 2, 2, 2\].

---

Sample Input 4

5 3 975576997

Sample Output 4

23

---

Sample Input 5

69 42 925171057

Sample Output 5

801835311