Problem Description

JYY led a team to several $\text{ACM/ICPC}$ contests and brought back many local specialties, which he wants to distribute to the students in the lab.

JYY wants to know: if these specialties are distributed to $n$ students, how many different distribution methods are there in total? Of course, JYY does not want any student to feel upset because they did not get any specialties, so each student must receive at least one specialty.

For example, JYY brought $2$ bags of twisted dough sticks and $1$ bag of buns, and distributes them to students $A$ and $B$. Then there are $4$ different distribution methods:

$A$: twisted dough stick, $B$: twisted dough stick, bun

$A$: twisted dough stick, twisted dough stick, $B$: bun

$A$: bun, $B$: twisted dough stick, twisted dough stick

$A$: twisted dough stick, bun, $B$: twisted dough stick

Input Format

Input testdata:

The first line contains the number of students $n$ and the number of specialty types $m$.

The second line contains $m$ integers, where each integer represents the quantity of one type of specialty.

$n, m$ do not exceed $1000$, and the quantity of each specialty type does not exceed $1000$.

Output Format

Output one line: the total number of different distribution plans.

Since the result may be extremely large, you only need to output the value of the final result $\bmod\ {10^9+7}$.

5 4
1 3 3 5

384835

Hint

Translated by ChatGPT 5