Chess Pieces Placement

Given an \(m\times n\) chessboard and \(c\) colors, you are also given \(r_1,r_2,\ldots,r_c\) which denote the number of pieces of each color that must be placed on the board. Each cell can have at most one piece. Pieces of different colors are not allowed to be in the same row or the same column. Pieces of the same color may share a row or a column. Count the number of ways to place the pieces satisfying these conditions.

More formally, let the board have rows \(1,2,\ldots,m\) and columns \(1,2,\ldots,n\). For each color \(i\) (\(1\le i\le c\)), exactly \(r_i\) pieces of that color are to be placed in cells such that if a cell \((x,y)\) contains a piece of color \(i\) and another cell \((p,q)\) contains a piece of color \(j\) with \(i\neq j\), then \(x\neq p\) and \(y\neq q\).

A typical example is: when \(m=n=3\), and there are 2 pieces of color 1 (say white) and 1 piece of color 2 (say gray), some placements are legal while others are not, as illustrated in the sample image.

inputFormat

The input consists of two lines. The first line contains three integers \(m\), \(n\) and \(c\) (the number of rows, columns, and colors respectively). The second line contains \(c\) non-negative integers \(r_1, r_2, \ldots, r_c\), where \(r_i\) is the number of pieces of the \(i\)-th color. Note that if \(r_i > 0\) then at least one row and one column must be allocated for that color.

It is guaranteed that \(m\) and \(n\) are small (for example, \(m,n\le 10\)) so that a brute force over row and column allocations is feasible.

outputFormat

Output a single integer: the number of valid placements of the pieces on the board that satisfy the conditions.

sample

3 3 2
2 1

126