AT_arc096_c [ARC096E] Everything on It

拉面店「高桥屋」的菜单基本上只有「拉面」一种，但还提供 $N$ 种配料。顾客在点拉面时，可以选择每种配料「加」或「不加」。加配料的数量没有限制，可以选择加所有配料，也可以一个都不加。也就是说，考虑配料的组合，一共有 $2^N$ 种不同的拉面可以点。 赤木小姐进入了高桥屋。她打算点若干碗拉面，使得同时满足以下两个条件： - 不会点多碗配料组合完全相同的拉面。 - 每一种配料，在所点的拉面中都至少出现了 $2$ 次。 给定 $N$ 和素数 $M$，请你求出满足上述条件的拉面组合数对 $M$ 取模的结果。拉面的顺序不计。由于赤木小姐极度饥饿，可以点任意多碗拉面。

输入从标准输入读入，格式如下： > $N$ $M$

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

## 限制 - $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 翻译