题目描述

小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共${m}$盆。通过调查顾客的喜好,小明列出了顾客最喜欢的${n}$种花,从${1}$到${n}$标号。

为了在门口展出更多种花,规定第i种花不能超过 ${a_i}$ 盆,摆花时同一种花放在一起,且不同种类的花需按标号的从小到大的顺序依次摆列。

试编程计算,一共有多少种不同的摆花方案。

输入格式

输入文件共${2}$行。第一行包含两个正整数${n}$和${m}$,中间用一个空格隔开。第二行有${n}$个整数,每两个整数之间用一个空格隔开,依次表示${a_1、a_2、……a_n}$。

输出格式

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

样例

样例输入

2 4
3 2

样例输出

2

数据范围与提示

【输入输出样例说明】

有 ${2}$ 种摆花的方案，分别是${(1，1，1，2)， (1，1，2，2)}$。括号里的 ${1}$ 和 ${2}$ 表示两种花，比如第一个方案是前三个位置摆第一种花，第四个位置摆第二种花。

数据范围

$对于 {20\%}数据，有 {0 < n \leq 8，0 < m \leq 8，0 \leq a_i \leq 8}；$

$对于 {50\%}数据，有 {0 < n \leq 20，0 < m \leq 20，0 \leq a_i \leq 20}；$

$对于 {100\%}数据，有 {0 < n \leq 100，0 < m \leq 100，0 \leq a_i \leq 100。}$