在一个 $n$ 行 $m$ 列的棋盘里放一些彩色的棋子，使得每个格子最多放一个棋子，且不同颜色的棋子不能在同一行或者同一列。有多少祌方法？例如，$n=m=3$，有两个白棋子和一个灰棋子，下面左边两祌方法都是合法的，但右边两祌都是非法的。
输入第一行为两个整数 $n, m, c$，即行数、列数和棋子的颜色数。
第二行包含 $c$ 个正整数，即每个颜色的棋子数。
所有颜色的棋子总数保证不超过 $nm$。
$N,M \le 30$，$C \le 10$ 总棋子数有大于 $250$的情况
输出仅一行，即方案总数除以 $1,000,000,009$ 的余数。
4 2 2 3 1
8
Comet OJ