시간 제한메모리 제한제출정답맞힌 사람정답 비율
7 초 512 MB666100.000%

문제

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

예제 입력 1

2 2 1000000007

예제 출력 1

2

예제 입력 2

3 4 1000000009

예제 출력 2

36

예제 입력 3

228 112263 998244353

예제 출력 3

379700769