← 返回题目列表

Codeforces · 1515/E

E. 凤凰城和计算机

中文机器翻译题面 查看原题

一排有 $$$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$$$ 为模的打开计算机的方式数。

示例

输入 #1

3 100000007

输出 #1

6

输入 #2

4 100000007

输出 #2

20

输入 #3

400 234567899

输出 #3

20914007

注意

在第一个示例中,这些是 Phoenix 可以打开所有计算机的 $$$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]$$$