如果你不想推公式。

钦定中间块颜色，转化成环染色。直接讨论 $1$ 与 $n-1$ 是否相同，如果相同，把 $1$ 到 $n-1$ 看成一个块，答案是 $(m-2)f(n-2)$，如果不同，直接忽略 $n$，令 $1$ 与 $n-1$ 相接，答案是 $(m-3)f(n-1)$。于是有 $f(n)=(m-2)f(n-2)+(m-3)f(n-1)$，矩阵加速即可。

#include<iostream>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
const int MOD=1e9+7;
int n,m;
struct matrix{
	int n,m;
	int num[2][2];
	matrix operator*(const matrix& mtrx)const{
		matrix res={n,mtrx.m,{{0,0},{0,0}}};
		if(m!=mtrx.n) return res;
		for(int i=0;i<n;i++)
			for(int j=0;j<mtrx.m;j++)
				for(int k=0;k<m;k++)
					(res.num[i][j]+=num[i][k]*mtrx.num[k][j])%=MOD;
		return res;
	}
}I={2,2,{{1,0},{0,1}}},A,T,Ans;
matrix qpow(matrix x,int b){
	matrix res=I;
	for(;b;b>>=1,x=x*x) if(b&1) res=res*x;
	return res;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	while(cin>>n>>m){
		if(n==1){
			cout<<m*(m-1)%MOD<<'\n';
			continue;
		}
		A={2,1,{{(m-1)*(m-2)%MOD},{0}}};
		T={2,2,{{m-3,m-2},{1,0}}};
		Ans=qpow(T,n-2)*A;
		cout<<Ans.num[0][0]*m%MOD<<'\n';
	}
	return 0;
}