题目描述

我们有一个长度为$N$的非负整数序列$A$。

对于所有满足$B$序列的和不超过$M$的序列$B$，计算$\\prod _{i = 1} ^N \\dbinom{B_i}{A_i}$ 的总和，并按照模 ($10^9 + 7$) 进行打印。

这里，$\\dbinom{B_i}{A_i}$ 表示从$B_i$个物体中选择$A_i$个物体的方式的数量，当$B_i < A_i$时为$0$。

约束条件

• 所有输入的值均为整数。
• $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$

输出

按照模 $(10^9 + 7)$ 打印$\\prod _{i = 1} ^N \\dbinom{B_i}{A_i}$ 的总和。

示例输入1

3 5
1 2 1

示例输出1

8

有四种满足$\\prod _{i = 1} ^N \\dbinom{B_i}{A_i}$ 不小于$1$的序列$B$：

• $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