Phoenix and Computers

题意翻译

给定 $n$，$M$。你有 $n$ 台电脑排成一排，你需要依次开启所有电脑。 你可以**手动**开启一台电脑。在任意时刻，若电脑 $i-1$ 与电脑 $i+1$ 都已经开启 $(1<i<n)$，电脑 $i$ 将立刻被**自动**开启。你不能再开启已经开启的电脑。 求你有多少种开启电脑的方案。两个方案不同当且仅当你**手动**开启的电脑的集合不同，或是**手动**开启电脑的顺序不同。答案对 $M$ 取模。

题目描述

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

输入输出样例

输入样例 #1

3 100000007

输出样例 #1

6

输入样例 #2

4 100000007

输出样例 #2

20

输入样例 #3

400 234567899

输出样例 #3

20914007

说明

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] $