The problem is to calculate the coefficients in expansion of polynomial (x₁+x₂+...+x_k)ⁿ.

Input

The input will consist of a set of pairs of lines. The first line of the pair consists of two integers n and k separated with space (0 < n, k <13). This integers define the power of the polynomial and the amount of the variables. The second line in each pair consists of k non-negative integers n₁, ..., n_k, where n₁+...+n_k=n.

Output

For each input pair of lines the output line should consist one integer, the coefficient by the monomial x₁ⁿ¹x₂ⁿ²...x_k^nk in expansion of the polynomial (x₁+x₂+...+x_k)ⁿ.

Example

Input:
2 2
1 1
2 12
1 0 0 0 0 0 0 0 0 0 1 0
Output:
2
2