/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
長さが N の非負整数列 A があります。
長さが N で、和が 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
出力
\prod _{i = 1} ^N \dbinom{B_i}{A_i} の総和を 10^9 + 7 で割った余りを出力せよ。
入力例 1
3 5 1 2 1
出力例 1
8
\prod _{i = 1} ^N \dbinom{B_i}{A_i} が 1 以上となるような数列 B の定め方は、以下の 4 通りです。
-
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
Score : 600 points
Problem Statement
We have a sequence A of N non-negative integers.
Compute the sum of \prod _{i = 1} ^N \dbinom{B_i}{A_i} over all sequences B of N non-negative integers whose sum is at most M, and print it modulo (10^9 + 7).
Here, \dbinom{B_i}{A_i}, the binomial coefficient, denotes the number of ways to choose A_i objects from B_i objects, and is 0 when B_i < A_i.
Constraints
- All values in input are integers.
- 1 \leq N \leq 2000
- 1 \leq M \leq 10^9
- 0 \leq A_i \leq 2000
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 \ldots A_N
Output
Print the sum of \prod _{i = 1} ^N \dbinom{B_i}{A_i}, modulo (10^9 + 7).
Sample Input 1
3 5 1 2 1
Sample Output 1
8
There are four sequences B such that \prod _{i = 1} ^N \dbinom{B_i}{A_i} is at least 1:
-
B = \{1, 2, 1\}, where \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\}, where \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\}, where \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\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{2}{2} \times \dbinom{2}{1} = 2.
The sum of these is 1 + 2 + 3 + 2 = 8.
Sample Input 2
10 998244353 31 41 59 26 53 58 97 93 23 84
Sample Output 2
642612171