测试数据来自 system/3056

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

染色

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　假设你有一条长度为 \(n\) 的木板，初始时没有染过任何颜色，现在你希望把它的每个单位长度都染上一种颜色。

　　已知可以使用的颜色有 \(m\) 种，从 \(1\) 到 \(m\) 标号。为了让木板上的颜色更加丰富，规定第 \(i\) 种颜色模板上的染色长度不能超过 \(a_i\) ，染色时同一种颜色必须是连续的一段，且不同颜色需按标号从小到大的顺序在木板上出现。

　　那么你一共有多少种不同的染色方案呢？请写一个程序来计算。

【输入格式】

　　第一行包含两个正整数 \(m\) 和 \(n\)，意义如题目描述。
　　第二行有 \(m\) 个整数，依次表示 \(a_1、a_2、…、a_m\)，分别表示每种颜色能染在木板上的最大长度。
　　同一行的每两个整数之间用一个空格隔开。

【输出格式】

　　输出一个整数，表示有多少种方案。因为这个数可能很大，只需输出对 1000007 取模的结果即可。

【输入输出样例】

　Input

3 6
3 1 4 

　Output

5

【样例说明】

　　木板长为6，可以使用3种颜色，标号分别为1,2,3，则有如下5种涂色方案：
　　　123333
　　　113333
　　　112333
　　　111233
　　　111333

【数据说明】

　　对于 \(20\%\) 的数据，\(0<m≤8，0<n≤8，0≤a_i≤8\)；
　　对于 \(50\%\) 的数据，\(0<m≤20，0<n≤20，0≤a_i≤20\)；
　　对于 \(80\%\) 的数据，\(0<m≤100，0<n≤100，0≤a_i≤100\)；
　　对于 \(100\%\) 的数据，\(0<m≤500，0<n≤20000，0≤a_i≤20000\)；

【来源】

　　Mr.he