Atcoder Educational DP Contest M - Candies

View as PDF

Submit solution


Points: 0.40 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout

Suggester:
Problem source:
Atcoder Educational DP Contest
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.