$$【组合数学】专题笔记目录$$

考虑 DP，设 $dp_i$ 表示最多填充 $i$ 种颜色的方案数。
这里做一个区分：题目中要求的是恰好 $C$ 种颜色。
那就可以表示出答案：$ans = \sum_{i=0}^{C} (-1)^{C - i} \binom{C}{i} \times dp_i$。

• 现在进行解释：由于 $dp_i$ 是最多的方案数，所以 $dp_i$ 包含 $dp_{1 \dots i-1}$，因此要容斥，系数就是 $(-1)^{C - i}$。
• 由于总共有 $C$ 种颜色，并且颜色之间没有区分（即可以任意选 $i$ 种颜色）所以要乘上系数 $\binom{C}{i}$，即 $C$ 种选$i$ 种。
• 最后肯定要乘上方案数 $dp_i$。

那如何求出 $dp_i$ 呢？考虑递推转移。
依旧可以容斥：$dp_i = \sum_{j=0}^{m} (-1)^{m-j} \times \binom{m}{j} \times ((i + 1)^j - 1)^n$

• 容斥就不多说了，显然这也是有“互相包含”的情况所以要容斥。
• 总共有 $m$ 列，每一列之间没有区分，所以 $\binom{m}{i}$。
• $((i + 1)^j - 1)^n$ 是因为每一个位置可以放 $i + 1$ 种（$i$ 种颜色和 $1$ 个不放颜色）由于每一行有 $j$ 个被选中，每一行就有 $(i + 1)^j$ 种方法。但是由于不能全空，所以要 $-1$，最后因为每一行都满足以上性质，所以要再 $n$ 次幂。

#include <bits/stdc++.h>
using namespace std;
const int N = 415;
const int mod = 1e9 + 7;
int n, m, C;

int qmi(int a, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = (res * 1ll * a) % mod;
        a = (a * 1ll * a) % mod;
        k >>= 1;
    }
    return res;
}

int fac[N], inv[N];
void init() {
    fac[0] = 1;
    for (int i = 1; i <= 400; i++) fac[i] = (fac[i - 1] * 1ll * i) % mod;
    inv[400] = qmi(fac[400], mod - 2);
    for (int i = 399; i >= 0; i--) inv[i] = (inv[i + 1] * 1ll * (i + 1)) % mod;
}

int c(int n, int m) {
    return ((fac[n] * 1ll * inv[m]) % mod * 1ll * inv[n - m]) % mod;
}

int dp[N];

int main() {
    scanf("%d%d%d", &n, &m, &C);
    init();
    for (int i = 1; i <= C; i++) {
        int x = 1;
        for (int j = m; j >= 1; j--) {
            int res = (x * c(m, j) * 1ll * qmi(qmi(i + 1, j) - 1, n)) % mod;
            dp[i] = (dp[i] * 1ll + res * 1ll + mod) % mod;
            x *= -1;
        }
    }
    // for (int i = 0; i <= C; i++) cout << dp[i] << ' '; puts("");
    long long ans = 0;
    int x = 1;
    for (int i = C; i >= 0; i--) {
        int res = (x * c(C, i) * 1ll * dp[i]) % mod;
        ans = (ans * 1ll + res * 1ll) % mod;
        x *= -1;
    }
    ans = (ans + mod) % mod;
    printf("%lld\n", ans);
    return 0;
}