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