分数: 800 点
问题陈述
有 N 儿童,已编号 1,2,\ldots,N。 在接下来的 K 天,我们会给他们一些饼干。 在 i第一天,我们会选择 a_i 儿童之中 N 以相同的概率,给每个被选中的孩子一块 cookie。 K 独立选择。)
让我们定义 幸福 的孩子们 c_1 \times c_2 \times \ldots \times c_N,其中 c_i 是 Child 收到的 cookie 数量 i 在 K 天。 找到预期的幸福乘以 \binom{N}{a_1} \times \binom{N}{a_2} \times \ldots \times \binom{N}{a_K} (我们可以证明这个值是一个整数),模 (10^{9}+7).
注释
\binom{n}{k} 表示可能的选择数量 k 给定不同的对象 n 对象,不考虑顺序。
约束
- 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 收到一个 cookie。
- 第二天,三个孩子中有两个 1, 2,和 3 收到一个 cookie。
- 他们的幸福是 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).