Restricted equation - MarisaOJ: Marisa Online Judge

Restricted equation

Time limit: 1000 ms
Memory limit: 256 MB

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