~Capoo~ hôm nay được phân nhiệm vụ phải trông ~N~ đứa trẻ được đánh số từ ~1~ đến ~N~. ~Capoo~ chuẩn bị sẵn ~K~ viên kẹo và dự định sẽ chia cho những đứa trẻ này, nhưng nghi ngờ rằng bọn trẻ có gen lập trình và tư duy thuật toán từ bố mẹ, ~Capoo~ đã đưa ra thử thách như sau:

• Với mỗi đứa trẻ, đứa thứ ~i~ ~(1 \le i \le N)~ phải nhận được số viên kẹo trong phạm vi từ ~0~ tới ~A_i~ và ~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.

Tàn ác hơn, bọn trẻ chỉ được nhận kẹo từ ~Capoo~ nếu đưa ra được đáp án chính xác. Một trong số những đứa trẻ đã cầu cứu bạn, hãy viết chương trình thỏa mãn yêu cầu của ~Capoo~ và bí mật cho những đứa trẻ này chép code nhé!

Dữ liệu

• Dòng đầu tiên là ~2~ số ~N~ ~(1 \le N \le 100)~ và ~K~ ~(0 \le K \le 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, A_3,...,A_N~ ~(0 \le A_i \le K)~.

Kết quả

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

Ràng buộc

• Subtask ~1~ ~(40\%)~: ~N = 2~.
• Subtask ~2~ ~(40\%)~: ~1 \le K \le 500~.
• Subtask ~3~ ~(20\%)~: Không có ràng buộc nào thêm.

Ví dụ

Dữ liệu

3 4
1 2 3

Kết quả

5

Giải thích

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.