You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

藤藤手里有 $K$ 个苹果，现在藤藤要把这些苹果分给 $n$ 个人，第$i$个人最多分$a_i$ 个苹果，当然你也可以一个都不给第$i$个人。

注意每个苹果都是无差别的，苹果都长的一样。问你藤藤分苹果的方案数。

由于答案很大， 结果对 $10^9 + 7$ 取余。

Format

Input

第一行两个整数 $n, K$

接下来$n$个整数，表示$a_1 \dots a_n$

Output

一个整数表示答案。

Samples

样例输入

3 4
1 2 3

样例输出

5

Limitation

$20\%$ 的测试数据，$0 \leq n, K \leq 10$

$50\%$ 的测试数据，$0 \leq n, K \leq 100$

$100\%$ 的测试数据，$0 \leq n \leq 100, 0 \leq K \leq 10^5$, $0 \leq a_i \leq K$