Kỳ thi Olympic Tin học Quốc tế sẽ được tổ chức tại thành phố Tsukuba, Nhật Bản. Để chuẩn bị cho IOI, chúng ta dự định xây dựng các tòa nhà chọc trời trên đường phố chính của thành phố. Vì muốn tạo ra một địa điểm tham quan mới, các tòa nhà phải thỏa mãn những điều kiện sau.

Có \(N\) tòa nhà được xây dọc theo một đường thẳng trên đường phố chính. Chiều cao của chúng là \(A_1,A_2,\ldots,A_N\), đôi một khác nhau. Thứ tự của các tòa nhà chưa được quyết định, nên ta có thể hoán vị các chiều cao này tùy ý.

Chúng ta sẽ trang trí các tòa nhà để chào đón IOI. Do giới hạn về vật liệu trang trí, tổng các trị tuyệt đối của hiệu chiều cao giữa hai tòa nhà kề nhau phải không vượt quá \(L\). Nói cách khác, nếu chiều cao các tòa nhà theo thứ tự nhìn từ một đầu của đường phố là \(f_1,f_2,\ldots,f_N\), thì phải có:

Ở đây, \(|x|\) là giá trị tuyệt đối của \(x\).

Có bao nhiêu hoán vị của các tòa nhà thỏa mãn điều kiện trên?

Yêu cầu

Cho số tòa nhà \(N\), chiều cao của chúng và giới hạn \(L\), hãy tính số hoán vị thỏa mãn điều kiện. Vì kết quả có thể rất lớn, hãy in phần dư của kết quả khi chia cho \(1\,000\,000\,007\).

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa hai số nguyên \(N,L\) cách nhau bởi một dấu cách: số tòa nhà và giới hạn trên của tổng các trị tuyệt đối của hiệu chiều cao giữa hai tòa nhà kề nhau.
• Dòng thứ hai chứa \(N\) số nguyên \(A_1,A_2,\ldots,A_N\) cách nhau bởi dấu cách. Số nguyên \(A_i\) là chiều cao của tòa nhà thứ \(i\) (\(1\le i\le N\)).

Dữ liệu ra

In một số nguyên trên một dòng ra đầu ra chuẩn: phần dư của số hoán vị thỏa mãn điều kiện khi chia cho \(1\,000\,000\,007\).

Ràng buộc

• \(1\le N\le 100\).
• \(1\le L\le 1\,000\).
• \(1\le A_i\le 1\,000\) với mọi \(1\le i\le N\).
• \(A_i\ne A_j\) với mọi \(1\le i<j\le N\).

Phân nhóm

1. 5 điểm: \(N\le 8\).
2. 15 điểm: \(N\le 14\) và \(L\le 100\).
3. 80 điểm: Không có ràng buộc bổ sung.

Ví dụ

4 10
3 6 2 9

6

    Với $(f_1,f_2,f_3,f_4)=(2,3,9,6)$:

    Với $(f_1,f_2,f_3,f_4)=(3,2,6,9)$:

    Với $(f_1,f_2,f_3,f_4)=(6,9,3,2)$:

    Với $(f_1,f_2,f_3,f_4)=(9,6,2,3)$:

    Với $(f_1,f_2,f_3,f_4)=(9,6,3,2)$:

8 35
3 7 1 5 10 2 11 6

31384