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 số lượng cách chọn các đồng xu có thứ tự để đạt được giá trị \(k\) là bao nhiêu?

Input

• Dòng đầu tiên gồm \(2\) số nguyên \(n,k\).
• Dòng thứ hai gồm \(n\) số nguyên khác nhau \(A_i\). Đảm bảo không có \(2\) loại xu cùng giá trị.

Output

• In ra một số nguyên, số lượng modulo \(10^9+7\)

Điều kiện

• \(1 \le n \le 10^{3}\)
• \(1 \le A_i, k \le 10^{5}\)

Sample Input 1

3 4
1 2 3

Sample Output 1

4

Giải thích

Có 4 cách: 1+1+1+1, 1+1+2, 1+3, 2+2