问题描述

在"高桥屋"这家拉面店里，基本上他们只有一份菜单："拉面"，但是还提供$N$种配料选择。当顾客点一碗拉面时，对于每一种配料，他/她可以选择是否将其放在拉面上。配料的数量没有限制，可以选择所有种类的配料或者不加配料。也就是说，考虑到配料的组合，可以点$2^N$种类型的拉面。

赤木走进了高桥屋。她打算点一些满足以下两个条件的拉面：

• 不点相同配料组合的多碗拉面。
• 每一种配料至少出现在两碗或者更多的拉面上。

给定$N$和一个质数$M$，找到满足这些条件的拉面组合的数量，忽略顺序，并对$M$取模。由于她非常饥饿，所以点任意碗数的拉面都可以。

约束条件

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

分数

• 如果通过满足$N ≤ 50$的测试集，则可获得600分。

---

输入

输入格式如下：

$N$ $M$

输出

打印满足条件的拉面组合的数量，忽略顺序，并对$M$取模。

---

示例输入1

2 1000000007

示例输出1

2

假设两种配料为A和B。可以点四种类型的拉面："不加配料"、"加A"、"加B"和"加A，B"。有两种拉面组合满足条件：

• 下面的三碗拉面："加A"、"加B"、"加A，B"。
• 四碗拉面，一种类型一碗。

---

示例输入2

3 1000000009

示例输出2

118

假设三种配料为A、B和C。除了上述四种拉面之外，还可以点四种类型的拉面，其中每种都添加了C。有$118$种满足条件的拉面组合，以下是其中的一些：

• 下面的三碗拉面："加A，B"、"加A，C"、"加B，C"。
• 下面的五碗拉面："不加配料"、"加A"、"加A，B"、"加B，C"、"加A，B，C"。
• 八碗拉面，一种类型一碗。

请注意，下面这组三碗拉面不满足条件："加A"、"加B"、"加A，B"，因为C没有出现在任何一碗拉面上。

---

示例输入3

50 111111113

示例输出3

1456748

请记得打印满足条件的数量，对$M$取模。请注意，上述这三个示例输入都包含在部分得分测试集中。

---

示例输入4

3000 123456791

示例输出4

16369789

这个示例输入不在部分得分测试集中。