#AT13. Candies
Candies
[M] Candies(dp_m)
来源: AtCoder Educational DP Contest - Problem M 原题时限:2 秒 / 内存:1024 MB
题目描述
有 个孩子,太郎打算给他们分糖果。
对于每个 (),第 个孩子能够分到的糖果数必须是 到 之间的整数。
太郎共需分出恰好 个糖果。求满足条件的分配方案数,对 取模。
输入格式
输入由标准输入按以下格式给出:
N K
a_1 a_2 \ldots a_N
输出格式
输出分配方案数对 取模的结果。
数据范围
- 输入中的所有值均为整数。
样例 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