爱丽丝这些天收到了很多礼物。于是她决定把它们装进盒子里寄给她的朋友们。
礼物有 $$$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\}$$$ 的方式是错误的,因为第一种礼物应该在至少一个盒子中使用。