Tổ hợp thuốc

Trong một dự án y tế mới, FullHouse Dev được giao nhiệm vụ phát triển một hệ thống tính toán các cách phối hợp thuốc. Họ cần tính toán số cách kết hợp các viên thuốc để đạt được một liều lượng cụ thể cho bệnh nhân. Đây là một bài toán quan trọng trong việc tối ưu hóa phác đồ điều trị.

Bài toán

Có \(n\) loại thuốc khác nhau. Mỗi viên thuốc có một giá trị đơn vị dương. Nhiệm vụ của bạn là tính toán số cách khác nhau để tạo ra tổng liều lượng \(x\) bằng cách sử dụng các viên thuốc có sẵn.

Ví dụ, nếu có các viên thuốc với giá trị {2,3,5} và tổng liều lượng cần đạt 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 đầu tiên chứa hai số nguyên \(n\) và \(x\): số lượng loại thuốc và tổng liều lượng cần đạt.
• Dòng thứ hai chứa \(n\) số nguyên \(c_1,c_2,\dots,c_n\): giá trị đơn vị của mỗi viên thuốc.

OUTPUT FORMAT:

• In ra một số nguyên: số cách kết hợp thuốc theo modulo \(10^9+7\).

Ràng buộc:

• \(1 \leq n \leq 100\)
• \(1 \leq x \leq 10^6\)
• \(1 \leq c_i \leq 10^6\)

Ví dụ

INPUT

3 9
2 3 5

OUTPUT

8

Giải thích

Với ba loại thuốc có giá trị đơn vị là 2, 3 và 5, để đạt được tổng liều lượng 9 đơn vị, có tổng cộng 8 cách kết hợp khác nhau như đã liệt kê ở trên. Mỗi cách thể hiện một phương án phối hợp thuốc khác nhau mà bác sĩ có thể cân nhắc cho bệnh nhân.