PreVOI 2024 - Money

Xem dạng PDF

Gửi bài giải

Điểm: 70,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout
Test chính thức

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

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Nhật là một đại gia với lượng tài sản khổng lồ. Nhật không thể mang theo toàn bộ số tiền của mình, nên hôm nay Nhật chỉ mang ~N~ mệnh giá khác nhau, bao gồm ~10^{100}~ tờ tiền có mệnh giá ~a_1~ đồng, ~10^{100}~ tờ tiền có mệnh giá ~a_2~ đồng, ~\dots~, ~10^{100}~ tờ tiền có mệnh giá ~a_N~ đồng.

Nhật muốn mua một mảnh đất có trị giá là ~K~. Với số tiền mà Nhật mang đi hôm nay, hãy tính số cách mà Nhật có thể mua mảnh đất.

Hai cách mua được coi là khác nhau nếu tồn tại một mệnh giá mà một cách mua sử dụng nhiều hoặc ít tờ tiền hơn cách mua còn lại.

Do số cách mua có thể rất lớn, hãy in ra phần dư của số cách mua sau khi chia lấy cho ~10^9 + 7~.

Input

Dòng đầu tiên ghi ~2~ số nguyên ~N, K~ ~(1 \le N \le 5000, 1 \le K \le 10^{18})~.

Dòng tiếp theo gồm ~N~ số nguyên phân biệt ~a_1, a_2, \dots, a_N~ ~(1 \le a_i \le K)~.

Output

In ra phần dư của đáp án của bài toán khi chia cho số ~(10^9 + 7)~.

Scoring

Gọi ~S~ là tổng ~a_1 + a_2 + \dots + a_N~.

Subtask Điểm Ràng buộc
1 ~10\%~ ~1 \le N \le 10, 1 \le K \le 10~.
2 ~40\%~ ~1 \le N \le 500, 1 \le K \le 5000~.
3 ~10\%~ ~N = 2, 1 \le K \le 10^9~.
4 ~40\%~ ~S \le 100~.

Sample Input 1

3 6
1 2 3

Sample Output 1

7

Notes

Có ~7~ cách mua như sau:

  • Dùng ~2~ tờ tiền ~3~ đồng

  • Dùng ~1~ tờ tiền ~3~ đồng, ~1~ tờ tiền ~2~ đồng, ~1~ tờ tiền ~1~ đồng

  • Dùng ~1~ tờ tiền ~3~ đồng, ~3~ tờ ~1~ đồng

  • Dùng ~1~ tờ ~2~ đồng, ~4~ tờ ~1~ đồng

  • Dùng ~2~ tờ ~2~ đồng, ~2~ tờ ~1~ đồng

  • Dùng ~3~ tờ ~2~ đồng

  • Dùng ~6~ tờ ~1~ đồng


Bình luận

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


Không có bình luận tại thời điểm này.