[CQOI2011]放棋子

题目描述

在一个 $m$ 行 $n$ 列的棋盘里放一些彩色的棋子,使得每个格子最多放一个棋子,且不同颜色的棋子不能在同一行或者同一列,有多少种方法? 例如,$n=m=3$,有两个白棋子和一个灰棋子,下面左边两种方法都是合法的,但右边两种都是非法的。 ![](https://cdn.luogu.com.cn/upload/pic/28150.png)

输入输出格式

输入格式


输入第一行为两个整数 $n,m,c$,即行数、列数和棋子的颜色数。 第二行包含 $c$ 个正整数,即每个颜色的棋子数。

输出格式


输出仅一行,即方案总数除以 $10^9+9$ 的余数。

输入输出样例

输入样例 #1

4 2 2
3 1

输出样例 #1

8

说明

$1\le n,m\le 30$,$1\le c\le 10$,总棋子数 $\le \min(250,n\times m)$。