#### UVALive 7040 / Gym 100548F – Color [容斥+数论]

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5052

### Analysis

14年西安网络赛的题。去年暑假组队赛也打过这道题，学姐推出来了，我写完TLE了，原因是当时不会逆元预处理。

### Code

```#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll maxn = 1024000, mod = 1000000007;
ll N, M, K;
ll C[maxn];
ll inv[maxn];

void initInv() {
inv[1] = 1;
for (int i = 2; i < maxn; i++)
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}

inline ll divMod(ll a, ll b) {
return a * inv[b] % mod;
}

ll quickpow(ll m, ll y) {
ll res = 1, base = m;
while(y > 0) {
if(y & 1)
res = (res * base) % mod;
base = (base * base) % mod;
y >>= 1;
}
return res % mod;
}

void getC(ll n, ll ed) {
C[0] = 1;
for(ll i = 1; i <= ed; ++i)
C[i] = divMod((C[i-1] * (n-i+1)) % mod, i);
}

ll solve() {
ll sum = 0;
ll flag = 1;
for(ll i = 0; i <= K - 1; ++i) {
ll cur = C[i] * (K - i) % mod;
cur = cur * quickpow(K - i - 1, N - 1) % mod;
sum = (sum + flag * cur + mod) % mod;
flag = -flag;
}
return sum;
}

int main() {
initInv();
int T, kase = 0; cin >> T;
while(T--) {
cin >> N >> M >> K;
getC(M, K); ll cmk = C[K];
getC(K, K);
int ans = (int) (cmk * solve() % mod);
printf("Case #%d: %d\n", ++kase, ans);
}
return 0;
}
```