分数: 100 点
问题陈述
有 N 儿童,已编号 1, 2, \ldots, N.
他们决定分享 K 糖果彼此之间。 在这里,对于每一个 i (1 \leq i \leq N),儿童 i 必须在 0 和 a_i 糖果(含)。 另外,糖果也不应该剩下。
求他们分享糖果的方式数,取模 10^9 + 7。 这里,当存在收到不同数量糖果的孩子时,两种方式被认为是不同的。
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 100
- 0 \leq K \leq 10^5
- 0 \leq a_i \leq K
输入
输入由标准输入按以下格式给出:
N K a_1 a_2 \ldots a_N
输出
打印孩子们分享糖果的方式数,取模 10^9 + 7.
示例输入 1
3 4 1 2 3
示例输出 1
5
孩子们分享糖果的方式有以下五种:
- (0, 1, 3)
- (0, 2, 2)
- (1, 0, 3)
- (1, 1, 2)
- (1, 2, 1)
这里,在每个序列中, i-第一个元素代表Child的糖果数量 i 收到。
示例输入 2
1 10 9
示例输出 2
0
孩子们可能没有办法分享糖果。
示例输入 3
2 0 0 0
示例输出 3
1
孩子们分享糖果的方式有一种,如下:
- (0, 0)
示例输入 4
4 100000 100000 100000 100000 100000
示例输出 4
665683269
请务必打印答案模数 10^9 + 7.