Sau khi giới thiệu tuyển thủ cho shiba, cậu ấy đã phần nào tin tưởng hơn _minhduc. Trùng hợp thay, lúc đó một biến cố đã xảy ra, đó là shiba bị bạn gái đá. Liệu chuyện gì sẽ xảy ra kế tiếp?

_minhduc là một đá thủ, chuyên sưu tầm các tảng đá. Hôm nay, bất ngờ tìm được một khu vực có "view triệu đô" - biển xanh, mây trắng, nắng vàng, _minhduc quyết định mang các tảng đá của mình tới để xây dựng thành một đoạn đường.

_minhduc có \(n\) tảng đá, tảng đá thứ \(i\) có trọng lượng là \(w_i\), khi nhảy lên trên chúng sẽ phát ra một loại âm thanh, để thuận tiện thì ta đánh số chúng trùng với trọng lượng của tảng đá, gọi là chất âm. Các tảng đá có thể khác nhau về trọng lượng cũng như chất âm, nhưng trọng bộ sưu tầm có rất nhiều đá của _minhduc vẫn có thể tồn tại hai hoặc nhiều tảng đá cùng trọng lượng và chất âm. _minhduc ban đầu xếp chúng thành một con đường thẳng, từ tảng đá thứ \(1\) cho tới tảng đá thứ \(n\). Khi nhảy từ tảng đá đầu tiên tới tảng đá cuối cùng, ta nhận được một "bản nhạc" khá vui tai. Sau đấy cậu ấy đã gọi điện cho bạn gái cũ của shiba để mời cô ấy đến thử đoạn đường này và ngắm nhìn khung cảnh tuyệt đẹp kia.

Tuy nhiên, ngay trước thời điểm cô ấy đến, _minhduc bỗng muốn thay đổi "bản nhạc" kia. Cậu ấy có thể làm thao tác sau vô số lần, đó là chọn hai tảng đá liền kề có tổng trọng lượng không quá \(k\) và đổi chỗ chúng. Sau khi đổi chỗ, cậu ấy sẽ lại thử nhảy từ tảng đá thứ \(1\) tới tảng đá thứ \(n\) và lại thu được một "bản nhạc".

Cậu ấy tự hỏi, nếu cứ thực hiện các thao tác trên, sẽ thu được bao nhiêu "bản nhạc" khác nhau. Hai "bản nhạc" được coi là khác nhau nếu có ít nhất một vị trí mà chất âm của tảng đá giữa chúng khác nhau. ~Cậu ấy cần biết có bao nhiêu "bản nhạc" khác nhau để còn trổ tài "làm nhạc" cho cô bạn gái cũ của shiba biết chứ.~

Yêu cầu: Đếm số "bản nhạc" khác nhau có thể thu được.

Input

• Dòng đầu tiên chứa số nguyên dương \(\phi\) - số thứ tự của subtask chứa test đó \((1 \le \phi \le 6)\).

• Dòng tiếp theo chứa hai số nguyên dương lần lượt là \(N\) và \(K\) – lần lượt là số tảng đá và tổng trọng lượng tối đa của hai tảng đá liền kề _minhduc có thể chọn để hoán đổi \((1 \le N \le 3 \times 10^5, 1\le K \le 10^9)\).

• Dòng cuối cùng chứa \(N\) số nguyên dương \(w_1,w_2,...,w_N\) \((1 \le w_i \le 10^9)\).

Output

• In ra kết quả bài toán sau khi chia lấy dư cho \(10^9+7\).

Scoring

• Subtask \(1\) (\(10\%\) số điểm): Có \(N \le 7\).

• Subtask \(2\) (\(10\%\) số điểm): Có \(N \le 100\) và tất cả chất âm của các tảng đá đều khác nhau đôi một.

• Subtask \(3\) (\(15\%\) số điểm): Có \(N \le 1000\) và tất cả chất âm của các tảng đá đều khác nhau đôi một.

• Subtask \(4\) (\(20\%\) số điểm): Có \(N \le 1000\).

• Subtask \(5\) (\(25\%\) số điểm): Có \(N \le 10^5\) và tất cả chất âm của các tảng đá đều khác nhau đôi một.

• Subtask \(6\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

1
4 8
3 5 3 7

3