Hãy xem xét một hệ thống tiền bao gồm \(n\) đồng xu. Mỗi đồng xu có giá trị là một số nguyên dương. Nhiệm vụ của bạn là tính số lượng các cách khác nhau mà bạn có thể tạo ra một khoản tiền \(x\) bằng cách sử dụng các đồng xu có sẵn.

Ví dụ: nếu các đồng xu là \(\{2, 3, 5\}\) 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

• Dòng đầu vào đầu tiên có 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 có \(n\) số nguyên phân biệt biệt \(c_1, c_2, \ldots, c_n\): giá trị của mỗi đồng xu.

Output

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

Constraints

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

Example

Sample input

3 9
2 3 5

Sample output

8