Rumiru là một cô bé rất thích chơi với slime. Hôm nay, cô quyết định đến một cửa hàng để mua một số con về chơi. Trong cửa hàng có trưng bày \(n\) con slime, con thứ \(i\) từ trái sang phải có kích thước \(a_i\). Rumiru muốn mua một số con slime và gộp một số cặp lại với nhau để tạo thành ít nhất một con có kích thước đúng bằng \(s\), quy tắc gộp như sau:

• Chọn hai con slime bất kỳ có kích thước bằng nhau và gộp chúng lại thành một con mới có kích thước bằng tổng kích thước của hai con cũ.

Hãy giúp Rumiru đếm số cách mua thoả mãn điều kiện. Biết rằng, hai cách mua được xem là khác nhau khi tồn tại một con slime được mua ở cách này nhưng không được mua ở cách còn lại.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(s\) \((1 \leq n \leq 2 \times 10^5, 1 \leq s \leq 5 \times 10^3)\) lần lượt là số lượng con slime và kích thước slime mong muốn.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq s\)) là kích thước của các con slime.

Output

• Một số nguyên duy nhất là phần dư số cách mua khi chia cho \(10^9 + 7\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 2 \times 10^3\).
• Subtask \(3\) (\(10\%\) số điểm): \(a_1 = a_2 = \ldots = a_n\).
• Subtask \(4\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 2
1 1 2

5

5 4
1 1 2 3 4

18