CF1515E Phoenix and Computers

有 $n$ 台电脑排成一排，最初都处于关闭状态，Phoenix 想要将它们全部打开。他每次可以手动打开一台电脑。在任意时刻，如果第 $i-1$ 台和第 $i+1$ 台电脑都已经打开，那么第 $i$ 台电脑（$2 \le i \le n-1$）如果还未打开，则会自动打开。注意，Phoenix 不能手动打开已经被自动打开的电脑。 如果我们只考虑 Phoenix 手动打开电脑的顺序，有多少种不同的方法可以将所有电脑打开？如果手动打开的电脑集合不同，或者手动打开的顺序不同，则认为两种方案是不同的。由于方案数可能很大，请输出对 $M$ 取模的结果。

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

输出一个整数，表示将所有电脑打开的方案数对 $M$ 取模后的结果。

在第一个样例中，Phoenix 可以通过以下 $6$ 种顺序手动打开所有电脑： - $[1,3]$。先手动打开第 $1$ 台电脑，再打开第 $3$ 台。注意，在手动打开第 $3$ 台电脑后，第 $2$ 台电脑会自动打开，但我们只考虑手动打开的顺序。 - $[3,1]$。先手动打开第 $3$ 台电脑，再打开第 $1$ 台。 - $[1,2,3]$。依次手动打开第 $1$、$2$、$3$ 台电脑。 - $[2,1,3]$ - $[2,3,1]$ - $[3,2,1]$ 由 ChatGPT 4.1 翻译