← 返回题目列表

Codeforces · 660/E

E. 所有元组的不同子集

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

对于由 1 到 m(含)之间的 n 个整数组成的序列 a,将 f(a) 表示为 a 的不同子序列的数量(包括空子序列)。

给定两个正整数 n 和 m。设S是由1到m的数字组成的长度为n的所有序列的集合。计算 S 模 109 + 7 中所有 a 的总和 f(a)。

输入

唯一一行包含两个整数 n 和 m (1 ≤ n, m ≤ 106) — 数组中元素的数量以及元素的上限。

输出

打印唯一的整数 c — 所需的模 109 + 7 的总和。

示例

输入 #1

1 3

输出 #1

6

输入 #2

2 2

输出 #2

14

输入 #3

3 3

输出 #3

174