题目描述

某高新技术产业园区是一个 $m$ 行 $n$ 列的网格状街区。规划局计划在街区的某些交叉格点上建造一些不同部门的办公大楼。每个格点上最多只能建造一栋大楼。

为了保证各部门的数据隔离与信息安全，规划局提出了一个严格的保密限制：不同部门的大楼绝对不能处在同一行街区或同一列街区（但同一部门的多栋大楼可以处在同一行或同一列）。

现在已知一共有 $c$ 个不同的部门，且每个部门需要建造的大楼数量也是确定的。请你计算出，一共有多少种不同的建筑布局方案？

例如，当 $n=m=3$ 且有两个部门（甲部门需建 2 栋大楼，乙部门需建 1 栋大楼）时，合理的空间排布应当使得任意两栋不同部门的大楼在纵向和横向上都互不重叠。下面左边两种都是合法的，右边两种都不合法。

$$\begin{array}{cccc} \begin{array}{|c|c|c|} \hline \Large\circ & \Large\circ & \\ \hline & & \Large\bullet \\ \hline & & \\ \hline \end{array} & \begin{array}{|c|c|c|} \hline & \Large\bullet & \\ \hline \Large\circ & & \\ \hline & & \Large\circ \\ \hline \end{array} & \begin{array}{|c|c|c|} \hline & \Large\bullet & \\ \hline & & \Large\circ \\ \hline & \Large\circ & \\ \hline \end{array} & \begin{array}{|c|c|c|} \hline & & \\ \hline \Large\bullet & & \Large\circ \\ \hline & \Large\circ & \\ \hline \end{array} \end{array}$$

由于最终的方案数可能非常庞大，你只需要输出方案总数除以 $10^9+9$ 的余数。

输入格式

输入第一行包含三个正整数 $n,m,c$，分别表示街区的行数、列数和需要安置的部门数量。

第二行包含 $c$ 个正整数，依次表示每个部门需要建造的办公大楼数量。

输出格式

输出仅一行，包含一个整数，即满足条件的所有布局方案总数除以 $10^9+9$ 的余数。

样例 1

4 2 2
3 1

8

样例说明

数据范围

对于 $100\%$ 的测试数据，满足 $1\le n,m\le 30$，$1\le c\le 10$，$\texttt{总办公大楼数}\le n\times m$。