Bạn có một tập hợp gồm mệnh giá tiền xu: . Bạn có thể sử dụng mỗi mệnh giá không giới hạn số lần.
Ví dụ, nếu các mệnh giá là và tổng mục tiêu là , có 3 cách để tạo ra tổng này:
(thứ tự không quan trọng nên đây giống với ...)
Nhiệm vụ của bạn là tính số cách khác nhau để tạo ra tổng tiền . Trong bài toán này, thứ tự của các đồng xu không quan trọng, ví dụ và được coi là cùng một cách.
Yêu cầu: Hãy tính số cách, theo modulo .
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên và : số lượng mệnh giá và tổng tiền mục tiêu.
Dòng thứ hai chứa số nguyên : các mệnh giá tiền xu.
Kết quả: In ra số cách, theo modulo .
Ví dụ:
Dữ liệu:
3 9
2 3 5
Kết quả:
3
Giải thích:
Các cách là:
(thứ tự không quan trọng nên đây giống với ...)
