← 返回题目列表

Codeforces · 451/E

E. Devu 和鲜花

中文机器翻译题面 查看原题

Devu 想用鲜花装饰他的花园。他购买了 n 个盒子,其中第 i 个盒子包含 fi 朵花。一个盒子里的所有花都是相同的颜色(因此它们是无法区分的)。此外,没有两个盒子里有相同颜色的花朵。

现在 Devu 想从盒子里精确挑选 s 朵花来装饰他的花园。 Devu 想知道,他可以用多少种不同的方式从每个盒子里挑选鲜花?由于这个数字可能非常大,所以他要求你求这个数字对(109 + 7) 的模。

如果至少有一个盒子以这两种方式选择了不同数量的花,则 Devu 认为这两种方式是不同的。

输入

输入的第一行包含两个空格分隔的整数 n 和 s (1 ≤ n ≤ 20, 0 ≤ s ≤ 1014)。

第二行包含 n 个空格分隔的整数 f1, f2, ... fn (0 ≤ fi ≤ 1012)。

输出

输出一个整数 — Devu 可以以 (109 + 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}。