← 返回题目列表

Codeforces · 1236/B

B. 爱丽丝和礼物清单

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

爱丽丝这些天收到了很多礼物。于是她决定把它们装进盒子里寄给她的朋友们。

礼物有 $$$n$$$ 种。一种礼物是相同的(即无法区分两种相同类型的礼物)。不同种类的礼物是不同的(即两种不同种类的礼物是可以区分的)。爱丽丝拥有的每种礼物的数量都非常大,因此我们可以认为爱丽丝拥有无限数量的每种礼物。

另外,还有 $$$m$$$ 盒子。所有这些都是针对不同的人的,因此它们是成对不同的(考虑到 $$$m$$$ 朋友的名字写在盒子上)。例如,将第一种礼物放入第一个盒子而不放入第二个盒子,与将第一种礼物放入第二个盒子而不放入第一个盒子是不同的。

Alice 想按照以下规则包装礼物:

- 她不会在同一个盒子里装入超过一件每种礼物,因此每个盒子应该包含不同种类的礼物(即每个盒子包含 $$$n$$$ 种类的子集,允许空盒子);
- 对于每种礼物,至少应将一份礼物装入某个盒子中。

现在爱丽丝想知道有多少种不同的包装礼物的方法。请帮助她计算这个数字。由于答案可能很大,因此将其模 $$$10^9+7$$$ 输出。

请参阅示例及其注释以进行说明。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$,用空格分隔 ($$$1 \leq n,m \leq 10^9$$$)——爱丽丝拥有的礼物种类数量和盒子数量。

输出

打印一个整数——按照爱丽丝的规则包装礼物的方式数量,以 $$$10^9+7$$$ 为模计算

示例

输入 #1

1 3

输出 #1

7

输入 #2

2 2

输出 #2

9

注意

在第一个示例中,有七种包装礼物的方法:

$$$\{1\}\{\}\{\}$$$

$$$\{\}\{1\}\{\}$$$

$$$\{\}\{\}\{1\}$$$

$$$\{1\}\{1\}\{\}$$$

$$$\{\}\{1\}\{1\}$$$

$$$\{1\}\{\}\{1\}$$$

$$$\{1\}\{1\}\{1\}$$$

在第二个示例中,有九种包装礼物的方法:

$$$\{\}\{1,2\}$$$

$$$\{1\}\{2\}$$$

$$$\{1\}\{1,2\}$$$

$$$\{2\}\{1\}$$$

$$$\{2\}\{1,2\}$$$

$$$\{1,2\}\{\}$$$

$$$\{1,2\}\{1\}$$$

$$$\{1,2\}\{2\}$$$

$$$\{1,2\}\{1,2\}$$$

例如,$$$\{2\}\{2\}$$$ 的方式是错误的,因为第一种礼物应该在至少一个盒子中使用。