← 返回题目列表

AtCoder · dwacon6th_prelims_c

C. Cookie 分发

中文机器翻译题面 查看原题

分数: 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).