Tổ hợp xu

Trong một buổi làm việc với cục thuế, FullHouse Dev được giao nhiệm vụ phân tích các cách thức thanh toán thuế. Họ cần tính toán số cách khác nhau để tạo ra một số tiền cụ thể từ các mệnh giá xu có sẵn, nhằm giúp việc thu thuế được linh hoạt hơn.

Bài toán

FullHouse Dev được cung cấp một hệ thống tiền tệ gồm \(n\) đồng xu, mỗi đồng có một giá trị nguyên dương. Nhiệm vụ của họ là tính toán số cách khác nhau có thứ tự để tạo ra một số tiền \(x\) sử dụng các đồng xu có sẵn.

Ví dụ, nếu các đồng xu có mệnh giá là {2,3,5} và số tiền cần tạo là 9, sẽ có 3 cách:

• 2+2+5
• 3+3+3
• 2+2+2+3

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(x\): số lượng đồng xu và số tiền cần tạo.
• Dòng thứ hai chứa \(n\) số nguyên \(c_1, c_2, ..., c_n\): giá trị của từng đồng xu.

OUTPUT FORMAT:

• In ra một số nguyên: số cách có thể tạo ra số tiền 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

3

Giải thích

Có 3 cách khác nhau để tạo ra số tiền 9 từ các đồng xu có mệnh giá 2, 3 và 5:

• Cách 1: Sử dụng hai đồng 2 và một đồng 5
• Cách 2: Sử dụng ba đồng 3
• Cách 3: Sử dụng ba đồng 2 và một đồng 3