题目描述

社团活动结束后，仓库里剩下了 $m$ 种纪念品，第 $i$ 种纪念品有若干件，同一种纪念品之间没有区别。

现在要把这些纪念品分给 $n$ 位同学。同学之间是有区别的，每件纪念品都必须分出去，并且每位同学至少要拿到一件纪念品。

请计算一共有多少种不同的分配方案。答案可能很大，只需输出对 $10^9+7$ 取模后的结果。

输入格式

第一行包含两个整数 $n,m$，表示同学数量和纪念品种类数。

第二行包含 $m$ 个整数，第 $i$ 个整数表示第 $i$ 种纪念品的数量。

输出格式

输出一行一个整数，表示不同分配方案数对 $10^9+7$ 取模后的结果。

样例

5 4
1 3 3 5

384835

数据范围

$n,m$ 不超过 $1000$，每一种纪念品的数量不超过 $1000$。