CTDL> bài 26.A3 CTDL> bài Đổi tiền 3.
Đổi tiền 3.
Hãy xem xét một hệ thống tiền tệ của ngân hàng MB bao gồm n đồng xu. Mỗi đồng xu có một giá trị nguyên dương. Nhiệm vụ của bạn là tính số cách riêng biệt không xét đến thứ tự mà bạn có thể tạo ra số tiền x bằng cách sử dụng số tiền có sẵn. Ví dụ: nếu số xu là và tổng mong muốn là 9, có 3 cách: 2 + 2 + 5; 3 + 3 + 3; 2 + 2 + 2 + 3.
Input Format
Dòng nhập đầu tiên có hai số nguyên n và x: số xu và số tiền mong muốn. Dòng thứ hai có n số nguyên phân biệt c1, c2,…, cn: giá trị của mỗi đồng xu. (1≤n≤100; 1≤x≤10^6; 1≤ci≤10^6)
Constraints
.
Output Format
In ra kết quả lấy dư với 10^9 + 7
Ví dụ:
Dữ liệu vào
5 13
5 11 10 4 3
Dữ liệu ra
4
Comments