Devu và những bông hoa

Devu có $n$ hộp hoa. Hộp thứ $i$ chứa $f_i$ bông hoa cùng màu, và các hoa trong cùng một hộp là không phân biệt được. Không có hai hộp nào chứa hoa cùng màu.

Devu muốn chọn ra đúng $s$ bông hoa để trang trí khu vườn. Hãy đếm số cách chọn số hoa từ mỗi hộp sao cho tổng đúng bằng $s$ bông. Hai cách được coi là khác nhau nếu tồn tại ít nhất một hộp mà số hoa lấy ra từ hộp đó ở hai cách là khác nhau.

Nói cách khác, hãy đếm số bộ $(x_1,x_2,\dots ,x_n)$ thoả mãn $0\le x_i\le f_i$ với mọi $i$ và $x_1+x_2+\dots +x_n=s$.

Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên $n$ và $s$.
• Dòng thứ hai chứa $n$ số nguyên $f_1,f_2,\dots ,f_n$.

Dữ liệu ra

Một số nguyên duy nhất: số cách chọn hoa, lấy phần dư khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le n\le 20$
• $0\le s\le {10}^{14}$
• $0\le f_i\le {10}^{12}$

Ví dụ