题目描述

给出n 个盒子，每个盒子有 \(f_i\) 朵花，每个盒子的花颜色相同，不同盒子的花颜色不同，问有多少种方案能恰巧选出 s 朵花。方案很多，输出方案数模 \(10^9+7\) 的结果（来自同一个盒子的花的数量不同才认为是不同的方案）。

输入格式

第一行两个整数 n, s。
第二行 n 个整数 \(f_1\), \(f_2\), …, \(f_n\)。

输出格式

输出方案数。

样例1

输入

2 3
1 3

输出

2

样例2

输入

2 4
2 2

输出

1

样例3

输入

3 5
1 3 2

输出

3

数据范围

对于 30%的数据，1 \(\leq\) n \(\leq\) 10, 0 \(\leq\) s \(\leq\) 100，0 \(\leq\) fi \(\leq\) 100；
对于 100%的数据，1 \(\leq\) n \(\leq\) 20, 0 \(\leq\) s \(\leq\) \(10^{14}\)，0 \(\leq\) fi \(\leq\) \(10^{12}\)。

限制

1s, 128M

样例解释

样例 1：两种方式选择 3 朵花：\([1, 2]\)、\([0, 3]\)；
样例 2：一种方式选择 4 多花：\([2, 2]\)；
样例 3：三种方式选择 5 多花：\([1, 2, 2]\)、\([0, 3, 2]\)、\([1, 3, 1]\)。

来源

Codeforces451E
CWOI新高二专题测试十八