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

一行中有 $n$ 台计算机，初始时全部关闭，Phoenix 希望将它们全部打开。他将一台一台地手动开启计算机。在任意时刻，若第 $i-1$ 台和第 $i+1$ 台计算机均处于开启状态，则第 $i$ 台计算机（其中 $2 \le i \le n-1$）会自动开启（前提是它尚未开启）。注意：Phoenix 不能手动开启已经自动开启的计算机。

如果仅考虑 Phoenix 手动开启计算机的顺序，那么他有多少种方式可以最终开启所有计算机？若两个序列所包含的手动开启的计算机集合不同，或手动开启的顺序不同，则认为这两个序列是不同的。由于答案可能很大，请输出其对 $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.

第一行包含两个整数 $n$ 和 $M$（$3 \le n \le 400$；$10^8 \le M \le 10^9$），分别表示计算机的数量和模数。保证 $M$ 是质数。

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

输出一个整数——开启计算机的方案数对 $M$ 取模的结果。

In the first example, these are the $6$ orders in which Phoenix can turn on all computers:

• $[1,3]$. Turn on computer $1$, then $3$. Note that computer $2$ turns on automatically after computer $3$ is turned on manually, but we only consider the sequence of computers that are turned on manually.
• $[3,1]$. Turn on computer $3$, then $1$.
• $[1,2,3]$. Turn on computer $1$, $2$, then $3$.
• $[2,1,3]$
• $[2,3,1]$
• $[3,2,1]$

在第一个例子中，凤凰开启所有计算机的顺序共有 $6$ 种：

• $[1,3]$：先开启计算机 $1$，再开启计算机 $3$。注意，计算机 $2$ 会在计算机 $3$ 被手动开启后自动开启，但我们只考虑被手动开启的计算机的顺序。
• $[3,1]$：先开启计算机 $3$，再开启计算机 $1$。
• $[1,2,3]$：依次开启计算机 $1$、$2$、$3$。
• $[2,1,3]$
• $[2,3,1]$
• $[3,2,1]$