Distribution of Souvenirs

JYY has participated in several (\text{ACM/ICPC}) contests and brought back many souvenirs that he wishes to distribute among (n) students. In doing so, he wants to ensure that every student receives at least one souvenir. The souvenirs come in (m) different types, where the (i)-th type has (a_i) identical items. For each type, the number of ways to distribute (a_i) identical items among (p) students (allowing zero items to some students) is given by the stars and bars formula: [ \binom{a_i+p-1}{p-1} ]

However, since every student must receive at least one souvenir in the overall distribution (across all types), we need to use the principle of inclusion and exclusion. In particular, if we let [ F(k)=\binom{n}{k}\prod_{i=1}^m \binom{a_i+(n-k)-1}{(n-k)-1}, ] then the final answer is given by [ \text{Answer} = \sum_{k=0}^{n-1} (-1)^k F(k). ]

For example, if JYY has 2 bags of mahua and 1 bag of baozi (i.e. (a_1=2) and (a_2=1)) and there are 2 students, then the number of valid distributions is 4, corresponding to the following assignments:

1. Student A: mahua; Student B: mahua and baozi
2. Student A: two mahua; Student B: baozi
3. Student A: baozi; Student B: two mahua
4. Student A: mahua and baozi; Student B: mahua

Your task is to compute the number of valid distributions given the integers (n) and (m) followed by (m) integers (a_1, a_2, \dots, a_m).

inputFormat

The first line of input contains two integers (n) and (m) (the number of students and the number of souvenir types). The second line contains (m) integers (a_1, a_2, \dots, a_m), where (a_i) represents the number of souvenirs of the (i)-th type.

outputFormat

Output a single integer: the number of valid distributions in which every student receives at least one souvenir.

sample

2 2
2 1

4