COEF - Coeficientes


The problem is to calculate the coefficients in expansion of polynomial (x1+x2+...+xk)n.

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 n1, ..., nk, where n1+...+nk=n.

Output

For each input pair of lines the output line should consist one integer, the coefficient by the monomial x1n1x2n2...xknk in expansion of the polynomial (x1+x2+...+xk)n.

Example

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

Output:
2
2

hide comments
मोहन: 2014-07-09 08:56:42

my 70th :)

sarthak joshi: 2014-06-28 09:38:17

My 50th on spoj

candide: 2014-04-21 04:29:35

Problem statement doesn't warn you about leading and trailing blank lines ...

Bhavik: 2014-01-02 22:00:52

another trick goes in the bag....

P_Quantum: 2013-09-20 06:30:46

Easy maths..!!

abhi: 2013-08-23 16:28:42

getting WA give some more input...

Shubham Gupta: 2013-06-25 04:43:27

Thank u NAMANDEEP :)

Vaibhav Agarwal: 2013-06-15 18:06:18

Easy one..... with this i complete 100 problems on spoj :)

Ouditchya Sinha: 2013-05-26 16:43:51

Piece of cake.. :)


Added by:Coach UTN FRSF
Date:2010-06-02
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:http://uva.onlinejudge.org/external/101/10105.html