꽃 구매하기

상근이는 여자친구에게 줄 꽃을 정확히 $S$송이 사려고 한다.

동네에는 꽃집이 $N$개 있고, $i$번째 꽃집은 꽃을 최대 $f_i$송이까지 판다. 한 꽃집이 파는 꽃은 모두 색이 같고, 색이 같은 꽃끼리는 구분할 수 없다. 서로 다른 꽃집이 같은 색 꽃을 파는 경우는 없다.

그래서 구매 방법은 각 꽃집에서 몇 송이를 사는지로 정해진다. 즉 $0 \le x_i \le f_i$이고 $x_1 + x_2 + \cdots + x_N = S$인 정수 수열 $(x_1, x_2, \ldots, x_N)$의 개수를 세면 된다.

꽃을 정확히 $S$송이 사는 방법의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 $N$과 $S$가 주어진다. ($1 \le N \le 20$, $0 \le S \le 10^{14}$)

둘째 줄에 $f_1, f_2, \ldots, f_N$이 공백으로 구분되어 주어진다. ($0 \le f_i \le 10^{12}$)

꽃을 정확히 $S$송이 사는 방법의 수를 $10^9 + 7$로 나눈 나머지를 첫째 줄에 출력한다.