快速幂+递归

https://ac.nowcoder.com/acm/problem/14584
表示 个气球涂 种颜色的方案数，则

（不考虑1号与n号气球颜色是否相同的方案数 - 1号与n号气球颜色相同的方案数）

且：

#include <iostream>
#define LL long long
using namespace std;
const int maxn = 1e5+5;
const int M = 1e8+7;
LL mp(LL x,LL y,LL _M){
    LL ret = 1ll;
    for(;y;y>>=1,x=(LL)x*x%_M)
    if(y&1) ret=(LL)ret*x%_M;
    return ret%_M;
}
LL sol(LL n,LL k){
    if(n==2) return (LL)k*(k-1)%M;
    return ((LL)k*mp(k-1,n-1,M)%M-sol(n-1,k)+M)%M;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    LL n,k,T;
    cin>>T;
    while(T--){
        cin>>n>>k;
        cout<<sol(n,k)<<"\n";
    }
    return 0;
}