← 返回题目列表

AtCoder · arc110_d

D. 二项式系数很有趣

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

分数: 600 点

问题陈述

我们有一个序列 A of N 非负整数。

计算总和 \prod _{i = 1} ^N \dbinom{B_i}{A_i} 所有序列 B of N 总和最多为的非负整数 M,并以模 (10^9 + 7).

在这里, \dbinom{B_i}{A_i},二项式系数,表示选择的方式数 A_i 对象来自 B_i 对象,并且是 0 当 B_i < A_i.

约束

  • 输入中的所有值都是整数。
  • 1 \leq N \leq 2000
  • 1 \leq M \leq 10^9
  • 0 \leq A_i \leq 2000

输入

输入由标准输入按以下格式给出:

N M
A_1 A_2 \ldots A_N

输出

打印总和 \prod _{i = 1} ^N \dbinom{B_i}{A_i},模数 (10^9 + 7).


示例输入 1

3 5
1 2 1

示例输出 1

8

有四个序列 B 这样 \prod _{i = 1} ^N \dbinom{B_i}{A_i} 至少 1:

  • B = \{1, 2, 1\},其中 \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{2}{2} \times \dbinom{1}{1} = 1;

  • B = \{2, 2, 1\},其中 \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{2}{1} \times \dbinom{2}{2} \times \dbinom{1}{1} = 2;

  • B = \{1, 3, 1\},其中 \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{3}{2} \times \dbinom{1}{1} = 3;

  • B = \{1, 2, 2\},其中 \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{2}{2} \times \dbinom{2}{1} = 2.

这些的总和是 1 + 2 + 3 + 2 = 8.


示例输入 2

10 998244353
31 41 59 26 53 58 97 93 23 84

示例输出 2

642612171