思路：补集思想，快速幂

从正面想的话有点难度，从容斥定理的角度想了一会，发现重复的部分不会容斥。。。

我们从反面看，出现相邻相同数的方案=总方案数-未出现相邻相同数的方案

总方案，每个位置有m种选择，即m^n

未出现相邻相同数的方案,第一个位置m种选择，第二个位置m-1种选择（不与位置1重复），第三个位置m-1种选择（不与位置2重复）……，方案数为

然后关于次方的问题，如果我们用乘法一个个数去乘，会tle（1e12的范围）

我们用一手快速幂，将乘方的复杂度降到logn就能过了（不知道快速幂的小伙伴可以百度学一手）

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#include <set>
using namespace std;
#define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define _rep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define pb push_back
#define IOS ios::sync_with_stdio(false)
#define int long long
typedef long long ll;
const int mod=1e9+7;
int n,m;
ll qsm(ll a,ll b)
{ll ans=1,temp=a;while( b ){if( b&1 ) ans = (ans * temp)%mod;temp = (temp * temp)%mod;b>>=1;}return ans;
}
signed main()
{
//    /!!!
//    freopen("data.txt","r",stdin);//!!!IOS;cin>>n>>m;cout<<(qsm(m,n) - m*qsm(m-1,n-1)%mod+mod)%mod<<endl;
}