451E. E. Devu and Flowers

CF451E. Devu and Flowers

时限: 4 秒 | 内存: 256 MB | 输入: 标准输入 | 输出: 标准输出

Devu 想用花来装饰他的花园。他买了 $n$ 个盒子，第 $i$ 个盒子里有 $f_i$ 朵花。每个盒子里的花都是同一种颜色，因此在同一个盒子里的花没有区别。而且不同盒子里的花颜色也不相同。

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

如果存在至少一个盒子，在两种选法中选择的花的数量不同，Devu 就认为这两种方式是不同的。

输入格式

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

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

输出格式

输出一个整数，表示 Devu 可以选择 $s$ 朵花的不同方法数，结果对 $(10^9+7)$ 取模。

样例输入 1

2 3
1 3

样例输出 1

2

样例输入 2

2 4
2 2

样例输出 2

1

样例输入 3

3 5
1 3 2

样例输出 3

3

提示

样例 1：有两种选 $3$ 朵花的方法：${1,2}$ 和 ${0,3}$。

样例 2：选 $4$ 朵花的方法只有一种：${2,2}$。

样例 3：选 $5$ 朵花的方法有三种：${1,2,2}$，${0,3,2}$ 和 ${1,3,1}$。