시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
7 초 | 512 MB | 6 | 6 | 6 | 100.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$.
2 2 1000000007
2
3 4 1000000009
36
228 112263 998244353
379700769