凤凰与电脑

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

有 $n$ 台电脑排成一行，最初都处于关闭状态。你可以每次手动打开一台仍关闭的电脑。

任意时刻，如果第 $i-1$ 台和第 $i+1$ 台电脑都已打开，那么仍关闭的第 $i$ 台电脑会自动打开。已经自动打开的电脑不能再被手动打开。

只考虑手动打开电脑的顺序：如果手动打开的电脑集合不同，或顺序不同，就视为不同方案。求最终打开全部电脑的方案数，对 $M$ 取模。

输入格式

第一行两个整数 $n,M$。

输出格式

输出方案数对 $M$ 取模的结果。

样例输入 1

3 100000007

样例输出 1

6

样例输入 2

4 100000007

样例输出 2

20

样例输入 3

400 234567899

样例输出 3

20914007

数据范围

$3\le n\le400$，$10^8\le M\le10^9$，且 $M$ 为质数。