P3158 [CQOI2011] Placing Pieces

On an $m$-row by $n$-column board, place some colored pieces so that each cell contains at most one piece, and pieces of different colors cannot lie in the same row or the same column. How many ways are there? For example, when $n=m=3$, there are two white pieces and one gray piece. The two arrangements on the left below are valid, while the two on the right are invalid. 

The first line contains three integers $n,m,c$, which are the numbers of rows, columns, and colors. The second line contains $c$ positive integers, which are the number of pieces of each color.

Output a single line: the remainder when the total number of arrangements is divided by $10^9+9$.

For $100\%$ of the testdata, $1\le n,m\le 30$, $1\le c\le 10$, and the total number of pieces $\le n\times m$. Translated by ChatGPT 5