Page not loading? Try clicking here.
Placeholder

#3657

배열의 개수 2 2s 512MB

Problems

길이 N짜리 정수 배열 B와 정수 S가 주어진다. 다음 조건을 만족하는 길이 N짜리 정수 배열 A의 개수를 구하는 프로그램을 작성하여라.

 

  1. 0 ≤ A[i] ≤ B[i] (1 ≤ i ≤ N)
  2. A[1] + A[2] + … + A[N] = S​

Input

첫째 줄에 N, S가 주어진다. (1 ≤ N ≤ 20, 0 ≤ S ≤ 1014)

둘째 줄에 B[i]가 주어진다. (0 ≤ B[i] ≤ 1012)​ 


Output

 

만들 수 있는 배열 A의 개수를 1,000,000,007로 나눈 나머지를 출력한다.​


Example #1

2 3

1 3
2

Example #2

2 4

2 2
1

Example #3

3 5

1 3 2
3
You must sign in to write code.