ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

4774: Different Subsets For All Tuples

内存限制：256 MB 时间限制：2 S
题面：传统 评测方式：文本比较 上传者：
提交：1 通过：1
提交提交记录统计Web Board

题目描述

E. Different Subsets For All Tuples
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
For a sequence a of n integers between 1 and m, inclusive, denote f(a) as the number of distinct subsequences of a (including the empty subsequence).
You are given two positive integers n and m. Let S be the set of all sequences of length n consisting of numbers from 1 to m. Compute the sum f(a) over all a in S modulo 109+7.
Input
The only line contains two integers n and m (1≤n,m≤106) − the number of elements in arrays and the upper bound for elements.
Output
Print the only integer c − the desired sum modulo 109+7.
Examples
Input 
1 3
Output 
6
Input 
2 2
Output 
14
Input 
3 3
Output 
174

输入样例 复制

输出样例 复制

分类标签