← 返回题目列表

AtCoder · nomura2020_f

F. 排序游戏

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

分数: 1000 点

问题陈述

Takahashi 和 Snuke 想出了一个使用数字序列的游戏,如下:

  • 准备一个长度的序列 M 由之间的整数组成 0 和 2^N-1 (含): a = a_1, a_2, \ldots, a_M.

  • Snuke 首先执行以下操作,次数不限:

    • 选择一个正整数 d,并且对于每个 i (1 \leq i \leq M),以二进制形式,设置 d- 第一个最低有效位 a_i to 0。 (这里最低有效位被认为是 1-st 最低有效位。)
  • Snuke完成操作后,Takahashi尝试排序 通过执行以下操作一定次数,按升序排列 a 。这里 a 据说是按升序排列的 a_i \leq a_{i + 1} 对于所有人 i (1 \leq i \leq M - 1).

    • 选择两个相邻元素 a: a_i 和 a_{i + 1}。如果在二进制中,这些数字恰好有一位不同,则交换 a_i 和 a_{i + 1}.

有 2^{NM} 不同长度的序列 可以在游戏中使用的 M 由之间的整数组成 0 和 2^N-1 。

其中有多少个具有以下性质:如果在游戏中使用,无论Snuke如何操作,Takahashi总有办法按升序对序列进行排序?求计数模数 (10^9 + 7).

约束

  • 输入中的所有值都是整数。
  • 1 \leq N \leq 5000
  • 2 \leq M \leq 5000

输入

输入由标准输入按以下格式给出:

N M

输出

打印数字,模数 (10^9 + 7),具有以下属性的序列:如果在游戏中使用,无论 Snuke 的操作如何,Takahashi 总有办法按升序对序列进行排序。


示例输入 1

2 5

示例输出 1

352

考虑这种情况 例如 a = 1, 3, 1, 3, 1 。

  • 当每个元素的最低有效位 a 设置为 0, a = 0, 2, 0, 2, 0;
  • 当每个元素的第二个最低有效位 a 设置为 0, a = 1, 1, 1, 1, 1;
  • 当每个元素的最低两位有效位 a 设置为 0, a = 0, 0, 0, 0, 0.

在上述所有情况以及 Snuke 不进行更改操作的情况下 a,我们可以通过重复交换恰好一位不同的相邻元素来对序列进行排序。 因此,这个序列有一个属性:如果在游戏中使用,无论Snuke的操作如何,高桥总有办法按升序对序列进行排序。


示例输入 2

2020 530

示例输出 2

823277409