Problem G

Multinomial Coefficients

One of the first formulas we were taught in high school mathematics is MATH. Later on, we learned that this is a special case of the expansion $(a+b)^{n}$, in which the coefficient of $a^{k}b^{n-k}$ is the number of combinations of $n$ things taken $k$ at a time. We never learned (at least I never did...) what happens if instead of a binomial $a+b$ we have a multinomial $a+b+c+\ldots +x$.

Problem

Your task is to write a program that, given a multinomial MATH, $k\geqslant 1$, computes the coefficient of a given term in the expansion of $m^{n}$, $n\geqslant 1$. The given term is specified by a sequence of $k$ integer numbers $z_{1}$, $z_{2}$, $\ldots $, $z_{k}$, representing the powers of $a_{1}$, $a_{2}$, $\ldots $, $a_{k}$ in the expansion. Note that MATH. For example, the coefficient of $ab^{2}c$ in $(a+b+c)^{4}$ is $12$.

Input

The input file contains several test cases, each of them with three lines. The first line contains a number representing the value of $n$. The second line contains a number representing the value of $k$. The third line contains $k$ numbers, representing the values of $z_{1}$, $z_{2}$, $\ldots $,$z_{k}$. All test cases are such that $k\leqslant 100$ and the computed coefficient is less than $2^{31}$.

Output

For each test case, write to the output one line. This line contains one integer number representing the value of the coefficient of the term MATH in the expansion of MATH.

Sample Input 1

 
4
3
1 2 1

Sample Output 1

 
12

Sample Input 2

 
7
4
2 3 0 2

Sample Output 2

 
210
Pedro Guerreiro, MIUP'2003
(Portuguese National ACM Programming Contest)