Killjee recently went to his old school and saw a student distributing chocolates on the occasion of his birthday.

The student had m type of chocolates and $p_{i}$ number of $i_{th}$ type of chocolates. There were n people whom he had to give chocolates but it was not necessary to give a chocolate to each person but as, it was his birthday he wanted to distribute all chocolates he had.

Killjee being a puzzled person wonders in how many ways the student can distribute all his chocolates.

As, you all know killjee is noob in both maths and coding so he is asking you all to help him.

Print the number of ways $\% 10^9+7$ as, the answer can be very large.

INPUT

First line of input contain two space separated integers n and m.

Next line contain m space separated integers number of chocolate of each type .

OUTPUT

Output a single integer, answer to the problem.

CONSTRAINTS

$1 \le n,m \le 3000$

$1 \le p_i \le 10^7$