Có n loại mệnh giá tiền xu, mỗi loại có số lượng không giới hạn. Hãy đếm xem có bao nhiêu cách khác nhau để gộp các đồng xu lại sao cho tổng giá trị đúng bằng S.
Hai cách được coi là giống nhau nếu dùng số lượng mỗi loại mệnh giá như nhau (không quan tâm thứ tự lấy xu). Ví dụ với các mệnh giá {1,2} và S=3 có 2 cách: 1+1+1 và 1+2.
Vì kết quả có thể rất lớn, hãy in ra theo modulo 109+7. Đây là bài toán quy hoạch động đếm tổ hợp kinh điển.
Dòng đầu chứa hai số nguyên n và S. Dòng thứ hai chứa n số nguyên dương là các mệnh giá (đôi một khác nhau).
1≤n≤100; 0≤S≤104; 1≤ci≤104.
In ra số cách đổi đúng số tiền S, lấy modulo 109+7.
Ví dụ:
Đầu vào:
2 3
1 2
Đầu ra:
2
Giải thích:
Đang tải editor...