CTDL&GT bài 26.A2 CTDL&GT bài Đổi tiền 2.


LÀM BÀI

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Đổi tiền 2.

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 mà bạn có thể tạo ra số tiền x bằng cách sử dụng số xu có sẵn. Ví dụ: nếu số xu là và tổng mong muốn là 9, có 8 cách: 2 + 2 + 5; 2 + 5 + 2; 5 + 2 + 2; 3 + 3 + 3; 2 + 2 + 2 + 3; 2 + 2 + 3 + 2; 2 + 3 + 2 + 2; 3 + 2 + 2 + 2

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
12

Comments

There are no comments at the moment.

Zalo