條件限制

（1）棋盤的每一個小方格既可以染色（染成 C 種顏色中的一種），也可以不染色。
（2）棋盤的每一行至少有一個小方格被染色。
（3）棋盤的每一列至少有一個小方格被染色。
（4）每種顏色都在棋盤上出現至少一次。

題解

設全集為 \(U\) ，\(U\) 表示滿足條件（2）（3）的所有染色的方案（包括不合法的（4）限制）

設屬性 \(S_i\) 表示滿足第 \(i\) 個顏色出現的方案。則有如下：

計算任意 \(x\) 個 \(\overline{S_i}\) 的交集就是計算至多選擇 \(c-x\) 個顏色的方案數，我們記 \(f(x)\) 為最多使用 \(x\) 個顏色的方案數. 那么 \(f(c)=\left | U \right |\) . 為了滿足條件（3）， \(f(x)\) 也需要用到容斥（我們考慮子集為至多有 \(i\) 列上有顏色，容斥求出當 \(i=m\) 時的情況），有如下：

因此

帶入 \(f(c-i)\) 得到答案：

CODE

#include<cstdio>
using namespace std;

const int N=405;
const int P=1e9+7;
typedef long long ll;
ll c,m,n,ans;
ll C[N][N],f[N];

void binom_init(){
    for (int i=0;i<=400;i++) {
        C[i][0]=1;
        for (int j=1;j<=i;j++) 
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
    }
}

ll binpow(ll a,ll idx){
    ll res=1;
    while (idx){
        if (idx&1) res=(res*a)%P;
        a=(a*a)%P;
        idx>>=1;
    }
    return res%P;
}

int main(){
    scanf("%lld%lld%lld",&n,&m,&c);
    binom_init();
    for (int i=0;i<=c;i++){
        for (int j=0;j<=m;j++){
            ll d;
            if (j&1) d=-1;
            else d=1;
            f[i]=(f[i]+(d*C[m][j]*binpow((binpow(i+1,m-j))-1,n)))%P;
        }
    }
    for (int i=0;i<=c;i++){
        ll d;
        if (i&1) d=-1;
        else d=1;
        ans=(ans+(d*C[c][i]*f[c-i]))%P;
    }
    ans=(ans+P)%P;
    printf("%lld\n",ans%P);
    return 0;
}