AT_dp_m Candies

题目描述

有 $N$ 个孩子。孩子们被编号为 $1, 2, \ldots, N$。

他们要一起分配 $K$ 颗糖果。此时，对于每个 $i$（$1 \leq i \leq N$），第 $i$ 个孩子能分到的糖果数必须在 $0$ 到 $a_i$ 之间（包含 $0$ 和 $a_i$）。此外，所有糖果必须全部分完，不能有剩余。

请问有多少种不同的分配糖果的方法？请输出答案对 $10^9 + 7$ 取模后的结果。这里，若存在某个孩子分到的糖果数不同，则认为两种分配方法不同。

输入格式

输入以如下格式从标准输入给出。

$N$ $K$ $a_1$ $a_2$ $\ldots$ $a_N$

输出格式

输出分配糖果的方法数对 $10^9 + 7$ 取模后的结果。

输入输出样例 #1

输入 #1

3 4
1 2 3

输出 #1

5

输入输出样例 #2

输入 #2

1 10
9

输出 #2

0

输入输出样例 #3

输入 #3

2 0
0 0

输出 #3

1

输入输出样例 #4

输入 #4

4 100000
100000 100000 100000 100000

输出 #4

665683269

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 100$
• $0 \leq K \leq 10^5$
• $0 \leq a_i \leq K$

样例解释 1

分配糖果的方法共有 $5$ 种。对于每个序列，第 $i$ 个元素表示第 $i$ 个孩子分到的糖果数。

• $(0, 1, 3)$
• $(0, 2, 2)$
• $(1, 0, 3)$
• $(1, 1, 2)$
• $(1, 2, 1)$

样例解释 2

也有可能不存在任何一种分配糖果的方法。

样例解释 3

分配糖果的方法只有 $1$ 种。

• $(0, 0)$

样例解释 4

不要忘记将答案对 $10^9 + 7$ 取模后输出。

由 ChatGPT 4.1 翻译