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 ```