解读一下，大概就是一种颜色放进去就会占据一行一列，dp 状态就好想了：$f_{i,j,k}$ 表示恰好用完前 $k$ 种颜色的所有棋子，占据了 $i$ 行 $j$ 列的方案数。你把已经被占据的行列挪到㮟㮟角角，这就导出了一个子问题，在一个 $(n-i)\times(m-j)$ 的矩形中，使用恰好 $u$ 个棋子（注意不是种类，这也是子问题和原问题的区别）占据其中一些行列的方案数。
容易发现，我们比较关心的是占据的行列数，而其与整个 $(n-i)\times(m-j)$ 矩形的关联并不强（因为我们都可以把选出来的挪到㮟㮟角角），设占据了 $x$ 行 $y$ 列，最后把方案数乘 $\binom{n}{x}\binom{m}{y}$ 即可。于是设 $f'_{i,j,k}$ 表示用恰好 $k$ 个棋子填满 $i\times j$ 矩形的方案数。转移逐行考虑，上一行就填了 $j$ 个棋子，设当前行填了 $h$ 个棋子，有 $l$ 列是和上一行共享，则当前行有 $j+h-l$ 个格子有棋子，于是可以写出 $f'_{i,j+h-l,k+h}=\sum\sum\binom{j+h-l}{,j}\binom{j}{l}f'_{i-1,j,k}$。
看回到 $f$ 的转移，考虑新棋子所占据的行列数 $h,l$，则有 $f_{i-h,j-l,k}=\sum\sum\binom{i}{h}\binom{j}{l}f_{i,j,k-1}f'_{h,l,a_k}$。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+9;
int n,m,c,a[20],mx,coef[40][40]; ll fac[110],ifac[110],dp[11][50][50],dpsub[50][50][1000],ans;
inline ll C(const int i,const int j) { assert(i>=j); return coef[i][j]; }
char buf[1<<21],*p1=buf,*p2=buf;
#define Gc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int Gi() {
int x=0; char c=Gc(); bool f=0;
while(c<'0' || c>'9') f|=(c=='-'),c=Gc();
while(c>='0' && c<='9') x=x*10+(c&15),c=Gc();
return f?-x:x;
}
signed main() {
for(int i=0; i<=35; ++i) {
coef[i][0]=1;
for(int j=1; j<=i; ++j) coef[i][j]=(coef[i-1][j-1]+coef[i-1][j])%MOD;
}
n=Gi(); m=Gi(); c=Gi();
for(int i=1; i<=c; ++i) mx=max(mx,a[i]=Gi());
dpsub[0][0][0]=1;
for(int i=1; i<=n; ++i) {
for(int j=0; j<=m; ++j) {
for(int k=0; k<=mx; ++k) {
for(int h=1; h<=m; ++h) {
for(int l=0; l<=min(h,j); ++l) {
if(j+h-l<=m) (dpsub[i][j+h-l][k+h]+=C(j+h-l,j)*C(j,l)%MOD*dpsub[i-1][j][k]%MOD)%=MOD;
}
}
}
}
}
dp[0][n][m]=1;
for(int k=1; k<=c; ++k) {
for(int i=1; i<=n; ++i) {
for(int j=1; j<=m; ++j) {
for(int h=1; h<=i; ++h) {
for(int l=1; l<=j; ++l) (dp[k][i-h][j-l]+=C(i,h)*C(j,l)%MOD*dp[k-1][i][j]%MOD*dpsub[h][l][a[k]]%MOD)%=MOD;
}
}
}
}
for(int i=0; i<=n; ++i) {
for(int j=0; j<=m; ++j) ans+=dp[c][i][j],ans%=MOD;
}
printf("%lld\n",ans);
return 0;
}