303407: CF660E. Different Subsets For All Tuples

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Different Subsets For All Tuples

题意翻译

有一个长度为$n$的数列,每个位置上数字的值在$[1,m]$范围内,则共有$m^n$种可能的数列。分别求出每个数列中本质不同的子序列个数(包含空序列),然后求和,答案对$10^9+7$取模。($1\le n,m\le10^6$)

题目描述

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 $ 10^{9}+7 $ .

输入输出格式

输入格式


The only line contains two integers $ n $ and $ m $ ( $ 1<=n,m<=10^{6} $ ) — the number of elements in arrays and the upper bound for elements.

输出格式


Print the only integer $ c $ — the desired sum modulo $ 10^{9}+7 $ .

输入输出样例

输入样例 #1

1 3

输出样例 #1

6

输入样例 #2

2 2

输出样例 #2

14

输入样例 #3

3 3

输出样例 #3

174

Input

题意翻译

有一个长度为$n$的数列,每个位置上数字的值在$[1,m]$范围内,则共有$m^n$种可能的数列。分别求出每个数列中本质不同的子序列个数(包含空序列),然后求和,答案对$10^9+7$取模。($1\le n,m\le10^6$)

加入题单

上一题 下一题 算法标签: