← 返回题目列表

AtCoder · dp_m

M. 糖果

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

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