学步园

http://www.lydsy.com/JudgeOnline/problem.php?id=3294

啊哈哈哈做了近1.5h

好不容易把yxj的方法看懂了（其实是蒟蒻一直把题看错了），就打算A掉这道题

就把g数组的k从1-250都枚举了一遍

理论上TLE，bzoj上却RE！！！！？？？？

没找到为什么，突然发现k是没有参与递推的，又改了很久很久

最后因为少取了个模！！！！！找了半个多小时

貌似多比yxj乘了几个组合数

啊还是不要秀智商了，上代码——

//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
/************************************************
Code By willinglive    Blog:http://willinglive.cf
************************************************/
#define rep(i,l,r) for(int i=(l),___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=(r),___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
inline const int read()
{int r=0,k=1;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1;
for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';return k*r;}
/////////////////////////////////////////////////
const int mod=1000000009;
int n,m,c;
int a[15];
LL C[910][910];
LL f[20][35][35];
LL g[11][35][35];
/////////////////////////////////////////////////

/////////////////////////////////////////////////
void input()
{
    cin>>n>>m>>c;
    rep(i,1,c) cin>>a[i];
}
void solve()
{
	// C[]
	rep(i,0,900) C[i][0]=1;
	rep(i,1,900) rep(j,1,i)
	    C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	// g[]
	rep(k,1,c)
    rep(i,1,30) rep(j,1,30) if(i*j>=a[k])
    {
        g[k][i][j]=C[i*j][a[k]];
        rep(x,0,i) rep(y,0,j) if(x||y)
        {
            g[k][i][j]-=((g[k][i-x][j-y]*C[i][x])%mod)*C[j][y]%mod;
            if(g[k][i][j]<0) g[k][i][j]+=mod;
        }
        g[k][i][j]%=mod;
        if(g[k][i][j]<0) g[k][i][j]+=mod;
    }
	// f[]
	rep(i,1,n) rep(j,1,m) f[1][i][j]=g[1][i][j];
	rep(k,2,c)
	rep(i,1,n) rep(j,1,m)
	{
		rep(x,0,i) rep(y,0,j)
		{
			f[k][i][j]+=f[k-1][x][y]*g[k][i-x][j-y]%mod*C[i][i-x]%mod*C[j][j-y]%mod%mod;
			f[k][i][j]%=mod;
		}
	}
	LL ans=0;
	rep(i,0,n) rep(j,0,m) ans+=f[c][i][j]*C[n][i]%mod*C[m][j]%mod;
	cout<<ans%mod<<endl;
}
/////////////////////////////////////////////////
int main()
{
    #ifndef _TEST
    freopen("std.in","r",stdin); freopen("std.out","w",stdout);
    #endif
    input(),solve();
    return 0;
}