A14201 | Phoenix and Computers

There are $n$ computers in a row, all originally off, and Phoenix wants to turn all of them on. He will manually turn on computers one at a time. At any point, if computer $i-1$ and computer $i+1$ are both on, computer $i$ $(2 \le i \le n-1)$ will turn on automatically if it is not already on. Note that Phoenix cannot manually turn on a computer that already turned on automatically.

If we only consider the sequence of computers that Phoenix turns on manually, how many ways can he turn on all the computers? Two sequences are distinct if either the set of computers turned on manually is distinct, or the order of computers turned on manually is distinct. Since this number may be large, please print it modulo $M$ .

The first line contains two integers $n$ and $M$ ( $3 \le n \le 400$ ; $10^8 \le M \le 10^9$ ) — the number of computers and the modulo. It is guaranteed that $M$ is prime.

Print one integer — the number of ways to turn on the computers modulo $M$ .