#AT13. Candies

Candies

[M] Candies(dp_m)

来源: AtCoder Educational DP Contest - Problem M 原题时限:2 秒 / 内存:1024 MB

题目描述

有 NN 个孩子,太郎打算给他们分糖果。

对于每个 ii(1≤i≤N1 \le i \le N),第 ii 个孩子能够分到的糖果数必须是 00 到 aia_i 之间的整数。

太郎共需分出恰好 KK 个糖果。求满足条件的分配方案数,对 109+710^9 + 7 取模。

输入格式

输入由标准输入按以下格式给出:

N K
a_1 a_2 \ldots a_N

输出格式

输出分配方案数对 109+710^9 + 7 取模的结果。

数据范围

  • 输入中的所有值均为整数。
  • 1≤N≤1001 \le N \le 100
  • 0≤K≤1050 \le K \le 10^5
  • 0≤ai≤K0 \le a_i \le K

样例 1

输入:

3 4
1 2 3

输出:

5

样例 2

输入:

1 10
9

输出:

0

样例 3

输入:

2 0
0 0

输出:

1

样例 4

输入:

4 100000
100000 100000 100000 100000

输出:

665683269