题目描述

幼儿园里有 \(n\) 个小朋友，依次编号 \(1,2,\cdots,n\)。

园长有 \(m\) 个糖果要全部（没有剩余）分给小朋友们，规定对于第 \(i(1 \le i \le n)\) 个小朋友分得的糖果个数在 \([0,a_i]\)之间。

请计算有多少种分配糖果的方案，两种分配方案不同当且仅当存在某一个小朋友在两种方案中分得不同个数的糖果。

格式

输入格式

第一行包含两个整数 \(n,m\)。

第二行 \(n\) 个用空格隔开的整数 \(a_1,a_2,\cdots,a_n\)。

输出格式

输出一行包含一个整数，为满足条件的糖果分配方案数 \(mod \ 10^9+7\) 的结果。

样例1

输入样例1

3 4
1 2 3

输出样例1

5

样例解释

满足条件的糖果分配方案有如下 \(5\) 种：

\[(0,1,3),(0,2,2),(1,0,3),(1,1,2),(1,2,1)\]

限制

\(100\%\)的数据：\(1≤n≤100，0≤m≤10^5，0≤a_i≤m\)。