Ans = \sum\limits_{i=0}^{c} (-1)^{i} \binom{c}{i} f_{c-i}
含义：从 c 中选 i 种颜色， 乘上只选 c-i 的方案数，容斥系数：(-1)^i
现在我们来考虑怎么求 f_i。我们知道 n^{k} 的组合意义是将 k 个小球放入 n 个有区别的盒子中。那么我们可以认为每种盒子的颜色不同，每个小球上标了列标。所以总的给这一列染色（可以不染）的方案数为 (i+1)^m，(i+1) 是因为可以不染（可以认为没染颜色是一种颜色）。因为一全空为非法，所以减 1 后再进行 n 次幂（有 n 行，因为行之间独立）。
现在我们枚举选了多少列涂色，类似地计算：
f_i = \sum\limits_{k=0}^{m} (-1)^k \binom{m}{k} ((i+1)^k-1)^n
## Code
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int SIZE = 4e2 + 5;
const int mod = 1e9 + 7;
int n, m, c;
int inv[SIZE], fac[SIZE], f[SIZE];
namespace GTR {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
return *s++;
}
inline int read() {
int a = 0, b = 1, c = fetch();
while (c < 48 || c > 57) b ^= c == '-', c = fetch();
while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
return b ? a : -a;
}
} using GTR::read;
int qPow(int a, int b) {
int ans = 1ll;
for ( ; b; b >>= 1, a = a * a % mod) {
if (b & 1) ans = ans * a % mod;
}
return ans % mod;
}
void init() {
const int N = 4e2;
fac[0] = 1ll;
for (int i = 1; i <= N; ++ i) fac[i] = fac[i - 1] * i % mod;
inv[N] = qPow(fac[N], mod - 2ll);
for (int i = N - 1; ~i; -- i) inv[i] = inv[i + 1] * (i + 1) % mod;
}
int C(int x, int y) {
if (x < y) return 0ll;
return fac[x] * inv[y] % mod * inv[x - y] % mod;
}
signed main() {
n = read(), m = read(), c = read(); init();
for (int i = 1; i <= c; ++ i) {
f[i] = (qPow(i + 1, m) - 1ll + mod) % mod, f[i] = qPow(f[i], n) % mod;
int res = 0;
for (int k = 1; k <= m; ++ k) {
int pw = (qPow(i + 1, m - k) - 1ll + mod) % mod; pw = qPow(pw, n) % mod;
if ((k - 1) & 1) res = (res - (pw * C(m, k) % mod) + mod) % mod;
else res = (res + (pw * C(m, k) % mod)) % mod;
}
f[i] = (f[i] - res + mod) % mod;
}
int ans = f[c], res = 0;
for (int i = 1; i <= c; ++ i) {
if ((i - 1) & 1) res = (res - (C(c, i) * f[c - i] % mod) + mod) % mod;
else res = (res + (C(c, i) * f[c - i] % mod)) % mod;
}
printf("%lld\n", (ans - res + mod) % mod);
return 0;
}
```