Trong tiết học thể dục có \(n\) học sinh xếp thành một hàng, được đánh số từ 1 đến \(n\) từ trái sang phải. Học sinh thứ \(i\) có chiều cao là \(h_i\), không có hai bạn nào có cùng chiều cao.

Ta nói hai học sinh \(i\) và \(j\) không nhìn thấy nhau nếu ở giữa họ có một người cao hơn cả \(i\) lẫn \(j\); tức là tồn tại \(k\) (\(i \lt k \lt j\) hoặc \(j \lt k \lt i\)) sao cho \(h_k > h_i\) và \(h_k > h_j\).

Thầy giáo đang có \(m\) viên bi, và sẽ chọn ra một số bạn để bắt đầu một trò chơi. Cách chọn là hợp lệ nếu:

• Những bạn được chọn đôi một không nhìn thấy nhau.
• Tổng chiều cao của họ không vượt quá \(m\).

Sau khi chọn, thầy sẽ phát cho mỗi bạn số bi bằng đúng chiều cao của bạn đó.

Không chọn học sinh nào cũng được xem là một cách chọn hợp lệ.

Nhiệm vụ

Hãy đếm số cách chọn hợp lệ các học sinh như trên. Hai cách chọn được coi là khác nhau nếu tồn tại một học sinh được chọn trong cách này nhưng không được chọn trong cách kia.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương \(n\) và \(m\): số học sinh và số bi.
• Dòng thứ hai chứa \(n\) số nguyên dương \(h_1, h_2, ..., h_n\): chiều cao của các học sinh.

Kết quả:

• In ra một số nguyên duy nhất là số cách chọn hợp lệ, sau khi chia lấy dư cho \(1000000007\).

Input 1

6 8
1 6 4 7 5 3

Output 1

12

Giải thích: Những cách chọn hợp lệ cho test ví dụ là:

• {}; {1}; {2}; {3}; {4}; {5}; {6}; {1, 3}; {1, 5}; {1, 6}; {3, 6}; {1, 3, 6}

Ràng buộc:

• Trong tất cả các test: \(n \le 4000\); \(h_i \le m\).
• Có 20% số test với \(n \le 18\) và \(m \le 100\).
• Có 20% số test với \(n \le 36\) và \(m \le 200\).
• Có 28% số test với \(n \le 100\) và \(m \le 400\).
• Có 32% số test không có ràng buộc gì thêm.