警示后人

不要忘记特判n=1的情况，否则20pts

思路

我们分为三部分考虑（n为正整数，n为奇数，n位偶数）

• n为正整数： 考虑n个位置，随便填1-（m-1）的整数，可重复，即有 $（m-1）^n$ 种情况。我们只需要把两两重复的位置，选一个改成m即可。
• n为奇数： 考虑填的所有数都相同，这时候不管把奇数位还是偶数位改成m，都没法使两两不同（这里不再过多证明，请读者自行理解）。这时需要我们把这些情况（所有数都相同）减掉。我们填的是1-（m-1），所以减m-1种情况，答案即为：$(m-1)^n$ -（m-1）
• **n为偶数：**同样考虑填的所有数都相同，这时候把奇数位或者偶数位改成m，都可以使两两不同，而在第一部分中，我们只算了一种方法，要把另一种叫上，答案即为： $(m-1)^n$ +（m-1）

不要忘记判n=1！！！！！！！！！！

code

bool M1;
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define deb(x) cerr<<"l: "<<__LINE__<<"  "<<#x<<"="<<x<<'\n'
#define look_memory cerr<<abs(&M2-&M1)/1024.0/1024<<"MB\n"

namespace syr
{
	const ll M = 1e9+7;
	ll n, m;
	ll power (ll a, ll b) {
		ll ans = 1;
		while (b) {
			if (b&1) ans = ans*a%M;
			a = a*a%M;
			b >>= 1;
		}
		return ans;
	}
	void work()
	{
		while (cin>>n>>m) {
			if (n==1) cout<<m<<'\n';
			else if (n%2) cout<<(power(m-1, n)-(m-1)+M)%M<<'\n';
			else cout<<(power(m-1, n)+(m-1))%M<<'\n';
		}
	}
}

bool M2;

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	look_memory;
	syr::work();
	return 0;
}

左转:推导

打开电风扇！！！！！！！！！！！

使劲吹！！！！！！！！！！

注意到答案为：