Count the number of integer solutions of the following equation:
$$x_1+x_2+...+x_n=S$$
that satisfy:
$$0 \le x_1\le A_1$$
$$0 \le x_2\le A_2$$
$$\ldots$$
$$0 \le x_n\le A_n$$
### Input
- The first line contains 2 integers $n, S$.
- The second line contains $n$ integers $A_i$.
### Output
- Print the answer, modulo $10^9+7$.
### Constraints
- $1 \le n \le 20$.
- $1 \le A_i, S \le 10^{9}$.
### Example
Input:
```
3 6
1 4 2
```
Output:
```
3
```