摆花（flower）

NOIP 2012 复赛普及组真题。本 OJ 采用标准输入输出评测，无需文件重定向。

题目描述

小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共m 盆。通过调 查顾客的喜好，小明列出了顾客最喜欢的n 种花，从1 到n 标号。为了在门口展出更多种花， 规定第i 种花不能超过ai 盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到 大的顺序依次摆列。 试编程计算，一共有多少种不同的摆花方案。

输入格式

输入文件flower.in，共2 行。 第一行包含两个正整数n 和m，中间用一个空格隔开。 第二行有n 个整数，每两个整数之间用一个空格隔开，依次表示a1、a2、……an。

输出格式

输出文件名为flower.out。 输出只有一行，一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出 方案数对1000007 取模的结果。

样例1

flower.in flower.out 2 4 3 2

2

【输入输出样例说明】 有2 种摆花的方案，分别是(1，1，1，2)， (1，1，2，2)。括号里的1 和2 表示两种花， 比如第一个方案是前三个位置摆第一种花，第四个位置摆第二种花。

数据范围

对于20%数据，有 0<n≤8，0<m≤8，0≤ai≤8； 对于50%数据，有0<n≤20，0<m≤20，0≤ai≤20； 对于100%数据，有0<n≤100，0<m≤100，0≤ ai≤100。

----PAGE----

普及组

4．文化之旅 (culture.cpp/c/pas)