Buying Flowers

Time limit2sMemory limit512 MB

Summary

Count integer sequences x_i with 0 <= x_i <= f_i summing to S, where N <= 20 and S up to 1e14.

Level: Medium7 of 10
Topics: Combinatorics, Dynamic programming, Math, Bit manipulation
Solved: No attempts yet

Problem

Sanggeun wants to buy exactly $S$ flowers for his girlfriend.

There are $N$ flower shops in his neighborhood, and shop $i$ sells at most $f_i$ flowers. All flowers sold by one shop have the same color, and flowers of the same color cannot be told apart. No two shops sell the same color.

So a way of buying is decided by how many flowers he takes from each shop. Count the integer sequences $(x_1, x_2, \ldots, x_N)$ with $0 \le x_i \le f_i$ and $x_1 + x_2 + \cdots + x_N = S$ .

Write a program that counts the ways to buy exactly $S$ flowers.

Input

The first line contains $N$ and $S$ . ( $1 \le N \le 20$ , $0 \le S \le 10^{14}$ )

The second line contains $f_1, f_2, \ldots, f_N$ separated by spaces. ( $0 \le f_i \le 10^{12}$ )

Output

Print on the first line the number of ways to buy exactly $S$ flowers, modulo $10^9 + 7$ .

Examples3

Example 1
Input
```
2 3
1 3
```
Expected output
```
2
```
Example 2
Input
```
2 4
2 2
```
Expected output
```
1
```
Example 3
Input
```
3 5
1 3 2
```
Expected output
```
3
```