Description

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.

Input Format

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 Format

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

4 2 2
3 1

8

Hint

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