꽃 장식하기

성관이는 화단에 꽃을 심으려고 한다. 심을 꽃은 이미 $n$종류를 준비해 두었고, $i$번째 종류의 꽃은 $f_i$송이 있다. 같은 종류의 꽃은 서로 구분할 수 없다.

성관이는 준비한 꽃 중에서 정확히 $s$송이를 골라 화단에 심으려고 한다. 각 종류에서 고른 송이 수가 모두 같으면 같은 방법으로 센다. 꽃을 고르는 방법의 수가 매우 클 수 있으므로 $10^9+7$로 나눈 나머지를 구한다.

꽃을 고르는 방법의 수를 계산하는 프로그램을 작성하시오.

첫째 줄에 $n$과 $s$가 주어진다. ($1 \le n \le 18$, $1 \le s \le 10^{14}$)

둘째 줄에 $n$개의 정수 $f_1, f_2, \ldots, f_n$이 주어진다. ($0 \le f_i \le 10^{12}$)

꽃을 고르는 방법의 수를 $10^9+7$로 나눈 나머지를 한 줄에 출력한다.

아래에서 괄호 안의 수는 각 종류에서 고른 송이 수다.

첫 번째 예제에서 고르는 방법은 $(1, 2)$와 $(0, 3)$의 2가지다.

두 번째 예제에서 고르는 방법은 $(2, 2)$의 1가지다.

세 번째 예제에서 고르는 방법은 $(1, 2, 2)$, $(0, 3, 2)$, $(1, 3, 1)$의 3가지다.