Beautiful Sequence Unraveling

Time limit7sMemory limit512 MB

Summary

Count arrays of length n with values from 1 to k where no split point has prefix maximum equal to suffix minimum, modulo the prime p.

Level: Hard8 of 10
Topics: Math, Combinatorics, Dynamic programming
Solved: No attempts yet

Problem

You are the happy owner of a powerful tool called Beautiful Sequence Unraveler (BSU). BSU handles beautiful sequences well.

A beautiful sequence is an array $a_1, a_2, \ldots, a_n$ of $n$ integers such that there is no integer $i$ with $1 \le i < n$ and $\max\{a_1, \dots, a_i\} = \min\{a_{i + 1}, \dots, a_n\}$ .

You want to know how often such sequences occur. Count the beautiful sequences among all arrays of length $n$ whose integers are between $1$ and $k$ , inclusive. The count may be large, so print it modulo the prime $p$ .

Input

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.

Output

Print the answer modulo $p$ .

Examples3

Example 1
Input
```
2 2 1000000007
```
Expected output
```
2
```
Example 2
Input
```
3 4 1000000009
```
Expected output
```
36
```
Example 3
Input
```
228 112263 998244353
```
Expected output
```
379700769
```