21120번 - 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$.

제한

힌트