12998번 - 꽃 장식하기

성관이는 화단에 꽃을 심고 싶다. 성관이는 이미 화단에 심을 꽃을 n종류 준비해둔 상태이다. i번째 종류의 꽃은 f_i 송이 있다. 또한, 같은 종류의 꽃은 서로 구분할 수 없다.

이제, 성관이는 화단에 심을 s송이의 꽃을 선택하고 싶다. 성관이는 꽃을 선택하는 방법의 수에 대해 알고 싶어한다. 이 방법의 수가 매우 클 수 있기 때문에, 10⁹+7로 나눈 나머지를 구할 것이다.

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

입력의 첫 번째 줄에는 n, s가 주어진다. (1 ≤ n ≤ 18; 1 ≤ s ≤ 10¹⁴)

다음 줄에는 n개의 자연수 f₁, f₂ … f_n이 주어진다. (0 ≤ f_i ≤ 10¹²)

꽃을 선택하는 방법의 수를 10⁹+7로 나눈 나머지를 출력하라.

입력 1은 {1,2}, {0,3}의 2가지 경우가 있다.

입력 2는 {2,2}의 1가지 경우가 있다.

입력 3은 {1,2,2}, {0,3,2}, {1,3,1}의 3가지 경우가 있다.