摆花（NOIP2012普及组）(多重背包求解方案数)

[NOIP2012 普及组] 摆花

题目描述

小明经营的花店刚刚开业，为了吸引更多顾客，他计划在店门口摆放一排花卉，总共需要 m 盆。通过对顾客偏好的调研，小明整理出了 n 种最受欢迎的花，并按照编号从 1 到 n 进行了标记。为了尽可能多地展示不同种类的花卉，规定第 i 类花卉的数量不得超过 a_i 盆。摆放时要求同一种类的花必须集中放置，并且各类花卉需按照编号从小到大的顺序依次排列。

请编写程序，计算满足上述条件的不同摆放方案总数。

输入格式

输入的第一行由两个正整数 n 与 m 构成，二者之间以一个空格作为分隔符。

第二行则包含 n 个整数，这些整数之间同样以空格进行分隔，依次对应 a_1,a_2, \cdots ,a_n。

输出格式

一个数值，用于表示可行的解决途径总数。需要说明的是，由于可能存在的方案数量较大，最终结果应以 10^6+7 为模数进行运算后输出。

样例分析与呈现

样例输入 #1

    2 4
    3 2
    
    
      
      
    

样例输出结构解析

    2
    
    
      
    

提示

数据范围

思路

对于第