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}。