407974: GYM102956 B Beautiful Sequence Unraveling

You are a happy possessor of the powerful tool called Beautiful Sequence Unraveler (BSU). This tool works with beautiful sequences. A beautiful sequence is an array $$$a_1, a_2, \ldots, a_n$$$ of $$$n$$$ integers for which the following statement holds: there are no integers $$$i$$$ such that $$$1 \le i < n$$$ and $$$\max\{a_1, \dots, a_i\} = \min\{a_{i + 1}, \dots a_n\}$$$.

BSU deals with beautiful sequences pretty well, but you do not know how frequently such sequences occur. So you want to calculate the number of beautiful sequences among all the arrays of length $$$n$$$ which consist of integers between $$$1$$$ and $$$k$$$, inclusively. Since this number may be large, you are required to calculate it modulo prime number $$$p$$$.

The only line contains three integers $$$n$$$, $$$k$$$, $$$p$$$ ($$$1 \le n \le 400$$$, $$$1 \le k \le 10^8$$$, $$$998\,244\,353 \le p \le 10^9 + 9$$$).

It is guaranteed that $$$p$$$ is prime.

Print the answer to the problem modulo $$$p$$$.

2 2 1000000007

2

3 4 1000000009

36

228 112263 998244353

379700769