题意简述：对n个排成一排的物品涂色，有m种颜色可选。

要求相邻的物品颜色不相同，且总共恰好有K种颜色，问所有可行的方案数。（$n,m\le 1e9,k\le 1e6$）

---

思路：

容斥原理套路：

先不考虑是否选全$k$种颜色，方案数为Cmk∗k∗(k−1)n−1C_m^k*k*(k-1)^{n-1}Cmk​∗k∗(k−1)n−1。

然后枚举剩下的至少有几种颜色没选来容斥掉非法情况：

于是Ans=Cmk∑i=k1(−1)k−iCkii(i−1)n−1Ans=C_m^k\sum_{i=k}^1(-1)^{k-i}C_k^ii(i-1)^{n-1}Ans=Cmk​∑i=k1​(−1)k−iCki​i(i−1)n−1

代码：

#include
    
     #define ri register intusing namespace std;const int N=1e6+5,mod=1e9+7;typedef long long ll;inline int read(){
    	int ans=0;	char ch=getchar();	while(!isdigit(ch))ch=getchar();	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();	return ans;}inline int add(const int&a,const int&b){
    return a+b>=mod?a+b-mod:a+b;}inline int dec(const int&a,const int&b){
    return a>=b?a-b:a-b+mod;}inline int mul(const int&a,const int&b){
    return (ll)a*b%mod;}inline int ksm(int a,int p){
    int ret=1;for(;p;p>>=1,a=mul(a,a))if(p&1)ret=mul(ret,a);return ret;}int n,m,k,C[N],inv[N],mult;inline void init(){
    	inv[1]=1;	for(ri i=2;i<=1000000;++i)inv[i]=mul(inv[mod-mod/i*i],mod-mod/i);}inline void Init(){
    	C[0]=1,mult=1;	for(ri i=1;i<=k;++i)C[i]=mul(mul(C[i-1],k-i+1),inv[i]);	for(ri i=1;i<=k;++i)mult=mul(mult,mul(m-i+1,inv[i]));}int main(){
    	init();	for(ri ans,tt=1,up=read();tt<=up;++tt){
    		n=read(),m=read(),k=read(),ans=0;		Init();		for(ri i=k,tmp;i;--i){
    			tmp=mul(C[i],mul(i,ksm(i-1,n-1)));			ans=(k-i)&1?dec(ans,tmp):add(ans,tmp);		}		cout<<"Case #"<
     <<": "<
      
       <<'\n';	}	return 0;}