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 < k < j\) hoặc \(j < k < i\)) sao cho \(h_{k} > h_{i}\) và \(h_{k} > h_{j}\). Thầy giáo đang có \(m\) viên bi, thầy sẽ chọn ra một số bạn để bắt đầu một trò chơi với các viên bi này. Cách chọn của thầy là hợp lệ nếu những bạn được chọn đôi một không nhìn thấy nhau, và tổng chiều cao của họ là bé hơn hoặc bằng \(m\) (sau đó, thầy đưa cho mỗi bạn số bi bằng đúng chiều cao của bạn đó và bắt đầu chơi). Thầy giáo bối rối vì có quá nhiều cách chọn hợp lệ, hãy giúp thầy tính toán con số này. Cụ thể, hãy đếm xem có bao nhiêu cách chọn ra một số học sinh sao cho những bạn được chọn đôi một không nhìn thấy nhau và tổng chiều cao của những bạn được chọn là bé hơn hoặc bằng \(m\). 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. Lưu ý, không chọn học sinh nào cũng được xem là một cách chọn hợp lệ.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương \(n\) và \(m\) là số học sinh và số bi;

• Dòng thứ hai chứa \(n\) số nguyên dương \(h_{1},\ h_{2},\ \ldots,\ h_{n}\) là chiều cao của các học sinh.

Kết quả:

Ghi 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.

Ví dụ:

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\ \leq 4000;\ h_{i} \leq m\).

• Có 20% số test với \(n\ \leq 18\) và \(m\ \leq 100\).

• Có 20% số test với \(n\ \leq 36\) và \(m\ \leq 200\).

• Có 28% số test với \(n\ \leq 100\) và \(m\ \leq 400\).

• Có 32% số test không có ràng buộc gì thêm.