Có ~N~ đứa trẻ được đánh số từ ~1~ tới ~N~.

Bọn trẻ quyết định chia nhau ~K~ viên kẹo. Với mỗi đứa trẻ, đứa thứ ~i (1 \leq i \leq N)~ phải nhận được số viên kẹo trong phạm vi từ ~0~ tới ~a_i~. ~K~ viên kẹo phải được dùng hết.

Hãy đếm số cách bọn trẻ có thể chia nhau những viên kẹo chia lấy dư cho ~10^9 +7~.

Hai cách chia được gọi là khác nhau nếu tồn tại một đứa trẻ nhận số viên kẹo khác nhau giữa hai cách.

Input

Dòng đầu tiên là hai số nguyên ~N(1 \leq N \leq 100)~ và ~K(0 \leq K \leq 10^5)~.

Dòng thứ hai có ~N~ số nguyên ~a_1,a_2,a_3,...,a_n (0 \leq a_i \leq K).~

Output

Số cách chia kẹo cho bọn trẻ chia lấy dư cho ~10^9 + 7~.

Sample 1

Input

3 4
1 2 3

Output

5

Có ~5~ cách để bọn trẻ chia nhau những viên kẹo như sau:

• ~(0,1,3)~
• ~(0,2,2)~
• ~(1,0,3)~
• ~(1,1,2)~
• ~(1,2,1)~

Ở mỗi dòng số thứ ~i~ là số lượng kẹo mà đứa trẻ thứ ~i~ nhận được.

Sample 2

Input

1 10
9

Output

0

Không có cách chia kẹo thỏa mãn.

Sample 3

Input

2 0
0 0

Output

1

Chỉ có ~1~ cách chia thõa mãn như sau:

• ~(0,0)~

Sample 4

Input

4 100000
100000 100000 100000 100000

Output

665683269

Hãy nhớ chia lấy dư kết quả cho ~10^9 + 7~.