题目：传送门。
题意：t组数据，每组给定n,m,k。有n个格子，m种颜色，要求把每个格子涂上颜色且正好适用k种颜色且相邻的格子颜色不同，求一共有多少种方案，结果对1e9+7取余。
题解：
首先可以将m 与后面的讨论分离。从m 种颜色中取出k 种颜色涂色，取色部分有C(m, k) 种情况；
然后通过尝试可以发现，第一个有k种选择，第二个因不能与第一个相同，只有(k-1) 种选择，第三个也只需与第二个不同，也有(k-1) 种选择。总的情况数为k ×(k-1)^(n-1)。但这仅保证了相邻颜色不同，总颜色数不超过k种，并没有保证恰好出现k种颜色；
接着就是一个容斥问题，上述计算方法中包含了只含有2、3、…、(k-1)种颜色的情况，需要通过容斥原理去除。假设出现p (2 <= p <= k-1)种颜色，从k种颜色中选取p种进行涂色，方案数为C(k,p) × p × (p-1)^(n-1)；
综上，最后的总方案数为C(m,k) × ( k × (k-1)^(n-1) + ∑((-1)^p × C(k, p) × p × (p-1)^(n-1) ) (2 <= p <= k-1)；
最后，需要注意1 ≤ n, m ≤10^9，在进行指数运算时，需要使用快速幂。对于组合数，只需要计算C(m,k)和C(k,p) (1 <= p <= k)，可以采用递推法，即C[x,i] = C[x, i-1] * (n-i+1) / i，因为要取模，所以需要用到i的逆元。
注意在总方案数的公式中p是大于等于2的，但是要特别注意当n=1的时候的情况，此时k只能为1，ans=m，如果k不为1，ans=0。
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int mod=1e9+;
const int maxn=1e6+;
typedef long long ll;
ll pow1(ll a,ll b)
{
ll ans=;
while(b)
{
if(b&) //b&1 而不是b 要注意
ans=ans*a%mod;
b>>=;
a=a*a%mod;
}
return ans;
}
ll inv[maxn];
void getinv()
{
for(int i=;i<maxn;i++)
inv[i]=pow1(i,mod-);//是i
}
ll cm[maxn],ck[maxn];
ll n,m,k;
void getmk()
{
cm[]=ck[]=;
for(int i=;i<=k;i++)
{
cm[i]=cm[i-]%mod*(m-i+)%mod*inv[i]%mod;
ck[i]=ck[i-]%mod*(k-i+)%mod*inv[i]%mod;
}
}
int main()
{
/*for(int i=0;i<50;i++)
cout<<pow1(0,i)<<endl;*/
// 0^0=1;
getinv();
int t,cas=;
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld%lld",&n,&m,&k);
getmk();
ll sgn=,ans=;
for(int i=k;i>=;i--) //一定要注意n=1的特殊情况
{
ans=(ans+sgn*ck[i]%mod*i%mod*pow1(i-,n-)%mod+mod)%mod;
sgn=-sgn;
}
ans=ans*cm[k]%mod;
printf("Case #%d: %lld\n",cas++,ans); //输出格式要严格 一定注意
}
return ;
}