E. Devu 与花

• 每个测试的时间限制：4 秒
• 内存限制：256 MB

Devu 想用花来装饰他的花园。他购买了 $n$ 个盒子，其中第 $i$ 个盒子里有 $f_i$ 朵花。
一个盒子里的所有花颜色相同（因此它们是不可区分的）。此外，任意两个盒子的花颜色不同。

现在 Devu 想从这些盒子中恰好选出 $s$ 朵花来装饰花园。
Devu 想知道，从每个盒子中选花的方式一共有多少种？
由于这个数字可能非常大，请你求出它对 $(10^9 + 7)$ 取模的结果。

Devu 认为两种方案不同，当且仅当存在至少一个盒子，在这两种方案中从该盒子选出的花数量不同。

---

输入格式

第一行包含两个用空格分隔的整数 $n$ 和 $s$（$1 \le n \le 20$，$0 \le s \le 10^{14}$）。

第二行包含 $n$ 个用空格分隔的整数 $f_1, f_2, \dots, f_n$（$0 \le f_i \le 10^{12}$）。

---

输出格式

输出一个整数 — 选花方式的总数，对 $10^9 + 7$ 取模。

---

输入输出样例

样例 1

输入：

2 3
1 3

输出：

2

样例 2

输入：

2 4
2 2

输出：

1

样例 3

输入：

3 5
1 3 2

输出：

3

---

样例解释

• 样例 1
  选 $3$ 朵花的方式有 2 种：
  $\{1, 2\}$（从第 1 个盒子选 1 朵，第 2 个盒子选 2 朵）
  $\{0, 3\}$（从第 1 个盒子选 0 朵，第 2 个盒子选 3 朵）

• 样例 2
  选 $4$ 朵花的方式只有 1 种：
  $\{2, 2\}$

• 样例 3
  选 $5$ 朵花的方式有 3 种：
  $\{1, 2, 2\}$、$\{0, 3, 2\}$、$\{1, 3, 1\}$