问题1134--装饰

1134: 装饰

时间限制: 1 Sec  内存限制: 128 MB
提交: 80  解决: 51
[状态] [提交] [命题人:]

题目描述

学校准备在文化长廊摆放一排装饰摆件,总共需要摆放 m 件。现有 n 种不同样式的摆件可供选择,每种摆件都有数量限制:第 i 种摆件最多只能使用 ai 件。
摆放要求:
  1. 相同样式的摆件必须放在一起,不能分开摆放;
  2. 所有摆件必须按照样式编号从小到大的顺序依次排列;
  3. 最终摆放的总件数恰好等于 m 件;
  4. 每种摆件可以选择不用(摆放 0 件)。
请你编程计算,一共有多少种不同的摆放方案?

输入

第一行包含两个正整数nnnmmm,中间用一个空格隔开。

第二行有nnn个整数,每两个整数之间用一个空格隔开,依次表示A1,A2,...,An

输出

一个整数,表示有多少种方案。注意:因为方案数可能很多,请输出方案数对100000710000071000007取模的结果。

样例输入 Copy

2 4
3 2

样例输出 Copy

2

提示

【数据范围】

对于20%数据,有0<n≤8,0<m≤8,0≤ai≤80<n≤8,0<m≤8,0≤a_i≤80<n8,0<m8,0≤Ai8


对于50%数据,有0<n≤20,0<m≤20,0≤ai≤200<n≤20,0<m≤20,0≤a_i≤200<n20,0<m20,0≤Ai20

对于100%数据,有0<n≤100,0<m≤100,0≤ai≤1000<n≤100,0<m≤100,0≤a_i≤1000<n100,0<m100,0≤Ai100

来源/分类