Xét một hệ thống tiền tệ với \(n\) loại đồng xu. Mỗi đồng xu có giá trị là một số nguyên dương. Hãy tính số cách khác nhau, không kể thứ tự để tạo ra tổng tiền \(x\) từ những đồng này.

Ví dụ: nếu các đồng xu là \(\{2, 3, 5\}\) và tổng mong muốn là \(9\), có \(3\) cách:

• \(2+2+5\)
• \(3+3+3\)
• \(2+2+2+3\)

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(x\): số lượng đồng xu và tổng số tiền mong muốn
• Dòng thứ hai chứa \(n\) số nguyên riêng biệt \(c_1, c_2, \ldots, c_n\): giá trị của mỗi đồng xu

Constraints

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

Output

• In một số nguyên duy nhất: số lượng cách, chia lấy dư cho \(10^9 + 7\)

Example

3 9
2 3 5

3