$n\times m$ 的棋盘，$c$ 种颜色的棋子，每种棋子共有 $x_i$ 个，每个格子只能放一个棋子，且不同颜色的棋子不能放在同一行或同一列上，求将所有棋子放在棋盘上的方案数。

$1\le n,m\le 30$，$1\le c\le 10$。

在上一题的基础上，本题扩展到了 $c$ 种颜色的棋子.

一个道理，设 $dp(i,j,k)$ 表示恰好前 $i$ 行前 $j$ 列恰好使用 $k$ 种棋子的方案数，$f(i,j,k)$ 表示恰好前 $i$ 行前 $j$ 列恰好使用一种、$x_k$ 个棋子的方案数，$x_k$ 表示至多 $i$ 行 $j$ 列使用一种 $x_k$ 个棋子的方案数。

则对于 $g$，显然有：

$$g(i,j,k)=C_{ij}^{x_k}$$

而对于 $f$，用 $g$ 对其做二项式反演即可，即：

$$f(i,j,k)=\sum_{p=0}^i\sum_{q=0}^j(-1)^{i+j-p-q}C_{i}^pC_j^qg(p,q,k)$$

$dp$ 的求解使用 $f$ 递推即可：

$$dp(i,j,k)=\sum_{p=0}^i\sum_{q=0}^jC_i^pC_j^qdp(i-p,j-q,k-1)f(p,q,x_k)$$

于是最终答案即为：

$$ans=\sum_{i=0}^n\sum_{j=0}^mC_n^iC_m^jdp(i,j,c)$$

总时间复杂度 $O(n^4k)$。

注意模数 *** 为 $10^9+9$！！！！

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=35;
const int M=1005;
const int V=1000;
const int mod=1e9+9;
int n,m,c,a[N],maxn;
ll inv[M],jc[M],g[N][N][N],f[N][N][N],dp[N][N][M];
int read(){
    int w=0,f=1;
    char ch=getchar();
    while (ch>'9'||ch<'0') {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9') {
        w=(w<<3)+(w<<1)+(ch^48);
        ch=getchar();
    }
    return w*f;
}
ll ksm(ll x,ll y){
    ll ans=1;
    while (y){
        if (y&1) ans=ans*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return ans;
}
void init(){
    jc[0]=inv[0]=1;
    for (int i=1;i<=V;i++) jc[i]=jc[i-1]*i%mod;
    inv[V]=ksm(jc[V],mod-2);
    for (int i=V-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
ll C(int x,int y){
    if (x<y) return 0;
    return jc[x]*inv[y]%mod*inv[x-y]%mod;
}
int main(){

    init();
    n=read(),m=read(),c=read();
    for (int i=1;i<=c;i++) a[i]=read(),maxn=max(maxn,a[i]);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            for (int k=1;k<=c;k++)
                g[i][j][k]=C(i*j,a[k]);//cout<<i<<" "<<j<<" "<<k<<" "<<a[k]<<" "<<g[i][j][k]<<"\n";
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            for (int k=1;k<=c;k++){
                for (int p=1;p<=i;p++){
                    for (int q=1;q<=j;q++){
                        ll x=((i+j-p-q)&1)?-1:1;
                        f[i][j][k]=(f[i][j][k]+x*C(i,p)*C(j,q)%mod*g[p][q][k]%mod+mod)%mod;
                    }
                }
                //cout<<i<<" "<<j<<" "<<k<<" "<<f[i][j][k]<<"\n";
            }
        }
    }
    dp[0][0][0]=1;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            for (int k=1;k<=c;k++){
                for (int p=1;p<=i;p++){
                    for (int q=1;q<=j;q++){
                        dp[i][j][k]=(dp[i][j][k]+C(i,p)*C(j,q)%mod*dp[i-p][j-q][k-1]%mod*f[p][q][k]%mod)%mod;
                        //if (i==3&&j==1&&k==1&&p==3&&q==1) cout<<dp[i][j][k]<<" "<<dp[i-p][j-q][k-1]<<" "<<f[p][q][a[k]]<<"\n";
                    }
                }
            }
        }
    }
    ll ans=0;
    for (int i=0;i<=n;i++)
        for (int j=0;j<=m;j++)
            ans=(ans+C(n,i)*C(m,j)%mod*dp[i][j][c]%mod)%mod;
    cout<<ans<<"\n";
    return 0;
}