Migrated from Lutece 3142 饮食计划

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

体测即将到来，由于测身高的机器存在明显的误差，Tri17计划通过调整饮食来控制自己的体重，让自己的BMI达标，从而减轻后面几学期体测的压力。

他为接下来的 $n$ 顿饭制定了饮食计划，总共有 $m$ 道菜在他的进食范围内，且每顿饭只会吃一个菜。同时，出于口感和营养的考虑，每种菜都存在进食数量上限，在这段时间内第 $i$ 个菜最多只能吃 $a_i$ 次。

如果两个计划方案上的所有食物种类与对应的数量都相同，即仅存在排列位次上的差异，则将被视为同一个方案。

Tri17想知道，一共有多少种不同的方案，好让他做出生活费上的预算支配。

Input

第一行包含两个正整数 $n,m$ ，分别表示饮食计划的持续时间和菜的种类数量。

第二行输入 $m$ 个整数，依次表示每个菜在计划内的最多出现次数。

Output

输出一个整数，表示方案的数量。 由于方案数可能会很多，请输出方案数模上 $10^9+7$ 后的答案。

Samples

4 2
2 3

2

5 3
2 3 1

3

4 2
10 10

5

Constraints

$1 \le n,m,a_i \le 10000$ 数据保证所有菜的进食次数上限之和不少于计划持续时间。

Note

对于样例1，存在 [2,2] , [1,3] 两种方案。 对于样例2，存在 [2,3,0] , [2,2,1] , [1,3,1] 三种方案。 对于样例3，存在 [0,4] , [1,3] , [2,2] , [3,1] , [4,0] 五种方案。

Resources

2024 UESTC ICPC Training for Search and Dynamic Programming