题目描述

拉面店「高桥屋」的菜单基本上只有「拉面」一种，但还提供 $N$ 种配料。顾客在点拉面时，可以选择每种配料「加」或「不加」。加配料的数量没有限制，可以选择加所有配料，也可以一个都不加。也就是说，考虑配料的组合，一共有 $2^N$ 种不同的拉面可以点。

赤木小姐进入了高桥屋。她打算点若干碗拉面，使得同时满足以下两个条件：

• 不会点多碗配料组合完全相同的拉面。
• 每一种配料，在所点的拉面中都至少出现了 $2$ 次。

给定 $N$ 和素数 $M$，请你求出满足上述条件的拉面组合数对 $M$ 取模的结果。拉面的顺序不计。由于赤木小姐极度饥饿，可以点任意多碗拉面。

输入格式

输入从标准输入读入，格式如下：

$N$ $M$

输出格式

输出满足条件的拉面组合数对 $M$ 取模的结果。

样例 1

输入

2 1000000007

输出

2

样例 2

输入

3 1000000009

输出

118

样例 3

输入

50 111111113

输出

1456748

样例 4

输入

3000 123456791

输出

16369789

说明/提示

限制

• $2 \leq N \leq 3000$
• $10^8 \leq M \leq 10^9 + 9$
• $N$ 是整数。
• $M$ 是素数。

部分分

• 对于满足 $N \leq 50$ 的测试点，得分为 $600$ 分。

样例解释 1

有 $2$ 种配料，分别为 A 和 B。可以点的拉面有「无配料」、「加 A」、「加 B」、「加 A 和 B」共 $4$ 种。满足条件的拉面组合有以下 $2$ 种：

• 「加 A」、「加 B」、「加 A 和 B」各一碗，共 $3$ 碗；
• 所有种类的拉面各一碗，共 $4$ 碗。

样例解释 2

有 $3$ 种配料，分别为 A、B、C。在样例 1 的 $4$ 种拉面基础上，再加上分别加 C 的 $4$ 种拉面。满足条件的拉面组合共有 $118$ 种，举例如下：

• 「加 A 和 B」、「加 A 和 C」、「加 B 和 C」各一碗，共 $3$ 碗；
• 「无配料」、「加 A」、「加 A 和 B」、「加 B 和 C」、「加 A、B、C」各一碗，共 $5$ 碗；
• 所有种类的拉面各一碗，共 $8$ 碗。 注意，「加 A」、「加 B」、「加 A 和 B」各一碗的 $3$ 碗组合不满足条件，因为 C 没有在任何一碗拉面中出现。

样例解释 3

不要忘记输出组合数对 $M$ 取模的结果。以上三个输入样例都包含在部分分的测试点中。

样例解释 4

本输入样例不包含在部分分的测试点中。

由 ChatGPT 4.1 翻译