Time Limit: 5000 MS Memory Limit: 65536 K

## Description

The black and white chess rooks were bored, so they decided to invite their
colorful friends to a party. However, as the evening progressed, many pairs of
rooks of different colors started arguing and threatening each other.
To prevent a massacre, you now need to place all the rooks in such a way that no
two rooks of different colors attack each other.
You are given the dimensions of the chessboard: ints rows and columns. You are
also given a vector counts, where counts[i] is the number of rooks of the
i-th color you have.
Compute and return the value (X mod 1,000,000,009), where X is the number of
valid arrangements of all the given rooks on the given chessboard. No square of
the chessboard may contain more than one rook. Rooks of the same color are
undistinguishable.
Two rooks attack each other if they are either in the same row or in the same column, and all squares between them are empty.
## Input

For each test case there is two lines.
The first line contains three integers rows,columns,N.
The second line contains N integers representing elements of counts.
rows will be between 1 and 30, inclusive.
columns will be between 1 and 30, inclusive.
counts will contain between 1 and 10 elements, inclusive.
Each element of counts will be positive.
The sum of all elements of counts will not exceed rows*columns.
## Output

For each test case output the answer on a single line:
## Sample Input

2 3 2
1 1
## Sample Output

12

## Source

srm 473