4. 物品染色

【题目描述】

有 $n$ 个物品要染色。一共 $m$ 种颜色。要求第 $i$ 种颜色不能染超过 $a_i$ 个物品。求方案数对 $10^9+7$ 取模后的结果。

【输入格式】

第一行两个整数 $n,m$。

第二行 $m$ 个整数 $a_i$。

【输出格式】

一行一个整数表示答案对 $10^9+7$ 取模后的结果。

【样例输入】

5 2
4 4

【样例输出】

30

【数据规模与约定】

对于 $30\%$ 的数据，$n,m \leq 5$

对于 $60\%$ 的数据，$n,m \leq 100$

对于 $80\%$ 的数据，$n,m \leq 3000$

对于 $100\%$ 的数据，$1 \leq n,m \leq 100000,a_i\times 2 >n，a_i \leq n$

【来源】

清北学堂2022 7.15模拟T3