407974: GYM102956 B Beautiful Sequence Unraveling
Description
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$$$.
InputThe 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.
OutputPrint the answer to the problem modulo $$$p$$$.
ExamplesInput2 2 1000000007Output
2Input
3 4 1000000009Output
36Input
228 112263 998244353Output
379700769