题目描述

有 $N$ 个孩子，编号为 $1,2,\\ldots,N$。在接下来的 $K$ 天里，我们会给他们一些饼干。在第 $i$ 天，我们以等概率从 $N$ 个孩子中选择 $a_i$ 个孩子，并给选择的每个孩子一个饼干。（我们独立地进行这 $K$ 次选择。）

让我们将孩子们的幸福度定义为 $c_1 \\times c_2 \\times \\ldots \\times c_N$，其中 $c_i$ 是孩子 $i$ 在 $K$ 天内收到的饼干数量。找出期望幸福度乘以 $\\binom{N}{a_1} \\times \\binom{N}{a_2} \\times \\ldots \\times \\binom{N}{a_K}$（我们可以证明这个值是整数），对 $(10^{9}+7)$ 取模。

注释

$\\binom{n}{k}$ 表示从给定的 $n$ 个不同对象中选择 $k$ 个对象的可能选择数，忽略顺序。

约束条件

• $1 \\leq N \\leq 1000$
• $1 \\leq K \\leq 20$
• $1 \\leq a_i \\leq N$

输入

输入以以下格式从标准输入给出：

$N$ $K$ $a_1$ $a_2$ $\\ldots$ $a_K$

输出

输出答案。

示例1

3 2
3 2

输出示例1

12

• 在第一天，孩子 $1$、$2$ 和 $3$ 都收到了一个饼干。
• 在第二天，从孩子 $1$、$2$ 和 $3$ 中选择 $2$ 个孩子收到了一个饼干。
• 无论如何，他们的幸福度都是 $4$，所以期望幸福度为 $4$。输出该值乘以 $\\binom{3}{3} \\times \\binom{3}{2}$，即 $12$。

示例2

856 16
399 263 665 432 206 61 784 548 422 313 848 478 827 26 398 63

输出示例2

337587117

• 计算期望值乘以 $\\binom{N}{a_1} \\times \\binom{N}{a_2} \\times \\ldots \\times \\binom{N}{a_K}$，对 $(10^9+7)$ 取模。