← 返回题目列表

AtCoder · arc096_c

E. 上面的一切

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

分数: 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

此示例输入不包含在部分分数的测试集中。