题目

Description

WYF画了一个极为不规则的n边形，画面太美简直不看，没有任意两条边长度是相等的。因为形状太难看了，做他同桌的CWQ看不下去了，趁着WYF上厕所的时间准备用他书包里的m种颜色的彩笔给n边形的边上色。但由于WYF画的实在太大，CWQ不知如何下手，他想知道他有多少种染色方法，能够使得每两条相邻 边不同色。你只需输出答案模10^9+7的结果。

Input

一行，仅包含两个正整数n和m。

Output

一个正整数，表示答案模10^9+7的结果

Sample Input

3 3

Sample Output

6

Data Constraint

对于50%的数据，3≤n≤100000，3≤m≤10；
对于100%的数据，3≤n≤10^18，3≤m≤50。

解析

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

int const mod=1e9+7;
long long n,m,fh;

long long ksm(long long x,long long y){
	long long ans=1;
	for(;y;y>>=1,(x*=x)%=mod) 
		if(y&1) (ans*=x)%=mod;
	return ans;
}

int main(){
	freopen("color.in","r",stdin);
	freopen("color.out","w",stdout);
	scanf("%lld%d",&n,&m);
	if(n&1) fh=-1;
		else fh=1;
	printf("%lld",(ksm(m-1,n)%mod+(m-1)*fh%mod+mod)%mod);
}