題目描述

𝑛n?個點排成一列，需要給每個點一個顏色，顏色有?𝑚m?種。請問有多少種方法，能使任意相鄰兩個點的顏色均不相同？

輸入格式

兩個整數：表示?𝑛n?與?𝑚m

輸出格式

單個整數：表示染色方案數模?1,000,000,0071,000,000,007?的余數。

數據范圍

• 對于?30%30%?的數據，1≤𝑛,𝑚≤101≤n,m≤10
• 對于?60%60%?的數據，1≤𝑛,𝑚≤100001≤n,m≤10000
• 對于?100%100%?的數據，1≤𝑛≤10151≤n≤1015
• 1≤𝑚≤1091≤m≤109

樣例數據

輸入:

3 2

輸出:

2

說明:

合法的染色方案有：{1,2,1} {2,1,2}?

詳見代碼:

#include<bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
long long f(long long k, long long p) 
{if(p == 1) return k;long long t = f(k, p / 2);if(p % 2 == 0) {return (t * t) % mod;}else {return (((t * t) % mod) * k) % mod;}}
int main() 
{long long n, m, ans;cin >> n >> m;ans = m * f(m - 1, n - 1) % mod;cout << ans << endl;return 0;
}