Solutions of a Diophantine Equation

Problem Description

Given the indeterminate equation $\sum_{i=1}^n x_i = m$ and $n$ constraints $x_i \leq b_i$, where $m, b_i \in \mathbb{N}$. Find the number of non-negative integer solutions to the equation.

Since the answer can be very large, output the result modulo $10^9 + 7$.

Input Format

The first line contains two integers $n, m$ ($1\leq n\leq 10, 1\leq m \leq 10^9$), followed by one line with $n$ integers $b_1, b_2, \dots, b_n$ ($1\leq b_i\leq m$).

Output Format

One number, the answer.

Sample Input

3 5
2 3 4

Sample Output

11

Constraints

For $100\%$ of the data, $1\leq n\leq 10, 1\leq m \leq 10^9, 1\leq b_i\leq m$.