老师教过一个公式， R n m = ( m − 1 ) n + ( m − 1 ) ⋅ ( − 1 ) n R_n^m=(m-1)^n+(m-1)\cdot(-1)^n Rnm​=(m−1)n+(m−1)⋅(−1)n
具体怎么证的忘了。。。

#include<bits/stdc++.h>
using namespace std;
const int M=10007;
int n,m;
int pw(int x,int y){
	int z=1;
	for (;y;y>>=1,x=x*x%M)
		if (y&1) z=z*x%M;
	return z;
}
int main(){
	scanf("%d%d",&n,&m);
	printf("%d",pw(m-1,n)+(n&1?-1:1)*(m-1));
}