有 N 个孩子和 K 颗糖果。

要把这 K 颗糖**全部**分完（一颗不剩），每个孩子分到的糖数不能超过他自己的上限：第 i 个孩子最多分 a_i 颗，**也可以一颗都不分**（分 0 颗合法）。

求满足

x_1+x_2+\cdots+x_N=K,\qquad 0\le x_i\le a_i

的整数分配方案 (x_1,\ldots,x_N) 的个数，对 10^9+7 取模。孩子之间是**有区别**的（第 1 个孩子分 1 颗、第 2 个孩子分 3 颗，与反过来是两种方案）。

第一行两个整数 N、K。

第二行 N 个整数 a_i。

一行一个整数：分配方案数 \bmod\ (10^9+7)。末尾换行。

**样例 #1 解释**

K=4、上限分别是 1,2,3 时，合法的 (x_1,x_2,x_3) 有 (0,1,3)、(0,2,2)、(1,0,3)、(1,1,2)、(1,2,1) 共 5 种。

**样例 #2/#3 解释**

只有一个孩子且上限 9<10，分不完，答案 0；K=0 时只有"谁都不分"这一种，答案 1。

| t1 | 20 | 20 | 3\le N\le6, K\le30 | 

| t2 | 20 | 40 | 15\le N\le20, K\le240, a_i\le40 | 

| t3 | 20 | 60 | 38\le N\le43, K\le6400, 200\le a_i\le500 | 

| t4 | 20 | 80 | 60\le N\le67, K\le64000, 1000\le a_i\le4000 | 

| t5 | 20 | 100 | 90\le N\le100, K\le10^5 |