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