大致题意： 有一个长度为(n)的数列，每个位置上数字的值在([1,m])范围内，则共有(m^n)种可能的数列。分别求出每个数列中本质不同的子序列个数，然后求和。
一些分析
首先，我们单独考虑空序列的个数(m^n)，然后接下来就可以只考虑非空序列的个数了。
假设有一个长度为(i)的子序列（(1le ile n)），且其在序列中的位置分别为(pos_1,pos_2,...,pos_i)，值分别为(val_1,val_2,...,val_i)。
则我们强制在(1sim pos_1-1)范围内不能出现(val_1)，(pos_1+1sim pos_2-1)范围内不能出现(val_2)，以此类推。
所以，在前(pos_i)个位置中，除(pos_{1sim i})这(i)个位置填(val_{isim i})外，如上所述，其余(pos_i-i)个位置各有(m-1)种填法。
而在第(pos_i)个位置之后就可以随便填了，每个位置都有(m)种填法。
推式子
通过之前的分析，于是得到式子如下：
对于这个式子的解释：
首先，用(i)枚举子序列长度，而长度为(i)的子序列共有(m^i)种可能。
接下来(j)枚举(pos_i)，而(pos_{1sim i-1})依次选择([1,pos_i-1])（即这里的([1,j-1])）这个范围内的任意位置都是合法的，就相当于在(j-1)个位置中选择(i-1)个位置，方案数就是(C_{j-1}^{i-1})。
从前文可得，(pos_i-i)（即这里的(j-i)）个位置有(m-1)种填法，(n-pos_i)（即这里的(n-j)）个位置有(m)种填法。
于是便得到上述式子。
然后就是化简：
先移项，把(m^i)移进去得到：
改变枚举顺序，得到：
观察到组合数中的(i-1)和(j-1)，不难想到直接将枚举的(i,j)减(1)，即：
然后我们可以化简一下系数，发现这些(1)和(-1)恰好抵消了，得到：
然后我们拎出(m^{n-j})，就可以得到：
那这样有什么好处呢？
回想一下二项式定理：((x+y)^n=sum_{i=0}^{n-1}x^iy^{n-i})。
这似乎与上面式子的后半部分有几分相似。
于是就可以化简得到：
这个式子可以(O(nlogn))快速幂计算，也可以直接(O(n))计算。
总而言之，可以过了。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 1000000
#define X 1000000007
#define Qinv(x) Qpow(x,X-2)
#define Inc(x,y) ((x+=(y))>=X&&(x-=X))
using namespace std;
int n,m;
I int Qpow(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}//快速幂
int main()
{
RI i,ans,p1,p2,b1,b2;
scanf("%d%d",&n,&m),ans=p1=Qpow(m,n),p2=1,b1=Qinv(m),b2=(1LL*2*m-1)%X;//初始化
for(i=0;i^n;++i) Inc(ans,1LL*p1*p2%X),p1=1LL*p1*b1%X,p2=1LL*p2*b2%X;//O(n)计算答案
return printf("%d",ans),0;//输出答案
}