Class Photo Arrangements

In this problem, you are given a class of n students with distinct heights and the requirement to arrange them in a formation with k rows for a class photo. The number of students in each row is pre‐determined and given in an order from the front row to the back row so that every row has no more students than the row behind it. When the rows are left‐aligned, the following two conditions must be satisfied:

• Every student (except the leftmost in a row) must be shorter than the student immediately to his left (i.e. the “row head” of his row).
• Every student (except those in the back row) must be shorter than the student directly behind him in the corresponding column.

If you reverse the order of the rows (i.e. consider the back row first, then the next row, …, and finally the front row), these conditions are equivalent to requiring that the numbers assigned to the students (their ranking when sorted from tallest to shortest) form a standard Young tableau of a given shape. In other words, if the k integers a₁,a₂,…,a_k are the numbers of students in each row of the formation in front-to-back order (so that a₁ ≤ a₂ ≤ … ≤ a_k and ∑a_i=n), then after reversing the order the shape becomes (a_k, a_k-1, …, a₁). The number of valid arrangements is exactly the number of standard Young tableaux of that shape, given by the famous hook-length formula:

$$\text{Answer} = \frac{n!}{\prod_{(i,j)\in\lambda} h(i,j)}, $$

where for each cell at row i and column j (in the reversed diagram), the hook-length h(i,j) is defined as

$$h(i,j)=\big(\lambda_i -j\big)+\big(\#\{l>i:\; \lambda_l\ge j\}\big)+1. $$

inputFormat

The input consists of two lines. The first line contains two integers n and k (n is the total number of students, and k is the number of rows). The second line contains k space‐separated integers denoting the number of students in each row, given in front-to-back order. It is guaranteed that the row counts are non-decreasing and sum to n.

outputFormat

Output a single integer — the number of valid arrangements that satisfy the conditions.

sample

6 3
1 2 3

16