[Cqoi2011]放棋子

时间限制:10s      空间限制:128MB

题目描述


输入格式

输入第一行为两个整数n, m, c,即行数、列数和棋子的颜色数。第二行包含c个正整数,即每个颜色的棋子数。所有颜色的棋子总数保证不超过nm


输出格式

输出仅一行,即方案总数除以 1,000,000,009的余数。


样例输入

4 2 2
3 1

样例输出

8

提示

N,M<=30 C<=10 总棋子数<=250


题目来源

没有写明来源