Dãy con có tổng bằng S

Xem dạng PDF

Gửi bài giải

Điểm: 8,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho dãy ~a~ gồm ~n~ số ~a_1, a_2, ..., a_n~, hãy đếm số lượng dãy con có tổng là ~S~, vì đáp án có thể rất lớn hãy in chia dư cho ~10^9 + 7~

Input

  • Dòng đầu gồm ~n~ và ~S~ (~1 ≤ n ≤ 100, 1 ≤ S ≤ 1000~)
  • Dòng tiếp theo gồm ~n~ số, số thứ ~i~ là giá trị của ~a_i~ (~1 ≤ a_i ≤ S~)

Output

  • Gồm một dòng duy nhất là đáp án cần tìm

Example

Input

3 2
1 1 1

Output

3

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 0
    qbojvn  đã bình luận lúc 27, Tháng 8, 2025, 13:30

    ez


  • 0
    skibidisaygex  đã bình luận lúc 27, Tháng 8, 2025, 12:39

    bài này giải kiểu gì ae tôi ngu quá