分数: 900 点
问题陈述
在拉面店“高桥屋”,基本上只有一个菜单:“拉面”,但是 还提供 N 各种配料。当顾客点一碗拉面时,对于每种配料,他/她可以选择是否将其放在他/她的拉面上。配料的数量没有限制,可以有各种配料,也可以不加配料。也就是说,考虑到配料的组合, 2^N 可以点拉面的种类。
赤木进入高桥屋。她正在考虑点几碗满足以下两个条件的拉面:
- 请勿点多碗配料完全相同的拉面。
- 每个 N 点的两碗或以上拉面的配料种类。
你被给予 N 和一个质数 M。求满足这些条件的拉面碗的组数,不考虑顺序,取模 M。因为她实在太饿了,所以点多少碗拉面都可以。
约束
- 2 \leq N \leq 3000
- 10^8 \leq M \leq 10^9 + 9
- N 是一个整数。
- M 是质数。
分项分数
- 600 通过满足以下条件的测试集将获得积分 N ≤ 50.
输入
输入由标准输入按以下格式给出:
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”。
- 八个拉面,每种一种。
请注意,以下三个集合不满足条件:“'with A'、'with B'、'with A, B'”,因为 C 不在其中任何一个上。
示例输入 3
50 111111113
示例输出 3
1456748
记住打印套数模数 M。请注意,上面的这三个示例输入包含在部分分数的测试集中。
示例输入 4
3000 123456791
示例输出 4
16369789
此示例输入不包含在部分分数的测试集中。