Dạo này, shiba có thói quen thích nghe nhạc. Cậu ấy quyết định mua một máy nghe nhạc (loại cũ) để thử cảm giác nghe nhạc của cuối những thập niên 90 :Đ.

Có tất cả \(n\) bài nhạc, bài nhạc thứ \(i\) dài đúng \(a_{i}\) phút. Máy nghe nhạc mà shiba mua ghi được tối đa \(m\) phút. Hỏi có bao nhiêu cách ghi nhạc khác nhau lên máy nghe nhạc, biết rằng mỗi bài nhạc chỉ được phép ghi một lần lên máy?

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n,m\) (\(n \le 1000, m \le 1000\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_{i}\) (\(a_{i} \le 1000\)).

Output

• Một số nguyên duy nhất là cách ghi nhạc lên máy nghe nhạc mà shiba có thể thực hiện, lấy phần dư cho \(10^9+7\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 6\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 20\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

3 4
1 5 6

1