Migrated from Lutece 3197 京东 E 卡

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

wwlw 抽奖抽到了一张京东 e 卡，内含 $s$ 元，但发现能买的东西不多，只能买京东自营的商品。浏览了一遍后，他决定只买点小零食。具体而言，现有 $n$ 种可以买的小零食，第 $i$ 种库存还有 $d_i$ 个。所有小零食单价都是 $1$ 元/个。他现在想知道，把这个卡里的钱花光有多少种方案。两种方案不同，当且仅当存在一种小零食在两个方案中买的个数不同。答案对 $10^9+7$ 取模。

Input

第一行，两个正整数 $n$ 和 $s$。

第二行，$n$ 个正整数，第 $i$ 个数表示 $d_i$。

Output

一个正整数，表示答案。

Samples

3 5
1 3 2

3

Constraints

$1\leq n\leq 20,1\leq d_i,s\leq 10^{14}$

Resources

2024 UESTC ICPC Training for Math