시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 7 4 4 57.143%

문제

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

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

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

입력

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

다음 줄에는 n개의 자연수 f1, f2 … fn이 주어진다. (0 ≤ fi ≤ 1012)

출력

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

예제 입력 1

2 3
1 3

예제 출력 1

2

예제 입력 2

2 4
2 2

예제 출력 2

1

예제 입력 3

3 5
1 3 2

예제 출력 3

3

힌트

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

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

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