Devu and Flowers

题号：NC230894
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Devu 想用花去装饰他的花园，他已经购买了 $n$ 个箱子，第 $i$ 个箱子有 $f_i$ 朵花，在同一个的箱子里的所有花是同种颜色的（所以它们没有任何其他特征）。另外，不存在两个箱子中的花是相同颜色的。

现在 Devu 想从这些箱子里选择 $s$ 朵花去装饰他的花园，Devu 想要知道，总共有多少种方式从这些箱子里取出这么多的花？因为结果有可能会很大，结果需要对 $10^9+7$ 取模。 Devu 认为至少有一个箱子中选择的花的数量不同才是两种不同的方案。

输入描述:

第一行包含两个用空格分开的整数和，。
第二行包含个用空格分开的整数。

输出描述:

输出一个整数表示答案。

示例1

输入

复制

2 3
1 3

输出

复制

说明

样例1：选3朵花两种方案：1,2 和 0,3

示例2

输入

复制

2 4
2 2

输出

复制

说明

样例2：选4朵花只有一种方案：2,2

示例3

输入

复制

3 5
1 3 2

输出

复制

说明

样例3：选5朵花三种方案：1,2,2 和 0,3,2 和 1,3,1

备注:

原题链接：http://codeforces.com/problemset/problem/451/E