Đồng xu 2

Có \(n\) loại xu lưu hành ở Gensokyo. Loại thứ \(i\) có giá trị \(A_i\). Marisa phải trả món nợ giá trị \(k\), hỏi có bao nhiêu cách chọn số lượng đồng xu mỗi loại (có thể dùng lại nhiều lần, không dùng loại nào cũng được) sao cho tổng giá trị các đồng xu đã chọn đúng bằng \(k\)?

Input

• Dòng đầu tiên gồm hai số nguyên \(n, k\) (\(1 \le n \le 1000\), \(1 \le k \le 10^5\)).

• Dòng thứ hai gồm \(n\) số nguyên khác nhau \(A_1, A_2, \ldots, A_n\) (\(1 \le A_i \le 10^5\)), đảm bảo không có hai loại xu cùng giá trị.

Output

In ra một số nguyên duy nhất, là số lượng cách chọn, lấy modulo \(10^9+7\).

Example

Input:

3 4
1 2 3

Output:

4

Note

Có \(4\) cách chọn số lượng đồng xu mỗi loại để tổng bằng \(4\):

• \(1 + 1 + 1 + 1\) (dùng 4 xu loại \(1\))

• \(1 + 1 + 2\) (dùng 2 xu loại \(1\), 1 xu loại \(2\))

• \(1 + 3\) (dùng 1 xu loại \(1\), 1 xu loại \(3\))

• \(2 + 2\) (dùng 2 xu loại \(2\))