Lilith là giáo viên dạy môn toán rời rạc cho lớp học của Koi. Để khuyến khích tinh thần tự học, cô Lilith dự định chia sinh viên trong lớp thành các nhóm ba người, các thành viên trong nhóm sẽ hỗ trợ nhau - học lực của ba người trong nhóm phải không quá chênh lệch nhau. Cô đánh giá học lực của mỗi sinh viên bằng một số tự nhiên từ \(1\) tới \(m\) rồi dựng một đa giác đều \(m\) đỉnh nội tiếp đường tròn (tâm \(O\)), các đỉnh của đa giác được đánh số từ \(1\) tới \(m\) theo chiều kim đồng hồ; nhóm sinh viên có điểm học lực lần lượt là \(a, b, c\) được cho là cân bằng khi và chỉ khi tam giác \(abc\) chứa \(O\).

Ví dụ nếu điểm học lực là từ \(1\) tới \(6\) thì cô Lilith có thể chia đường tròn như sau:

Với lớp có \(6\) học sinh với điểm học lực lần lượt là \(1, 2, 3, 4, 5, 6\), cô Lilith có đúng \(14\) cách lập nhóm thứ nhất: \(2\) cách lập thành tam giác đều (\(135\), \(246\)) và \(12\) cách lập thành tam giác vuông (\(3\) đường chéo đi qua tâm, mỗi đường chéo tạo \(4\) tam giác vuông) đều chứa tâm đường tròn.

Tiện thể đang trong giờ học, cô đố cả lớp xem có bao nhiêu cách lập nhóm đầu tiên. Koi đã nhanh chóng đếm trong trường hợp điểm học lực của các sinh viên là phân biệt, tuy nhiên cậu vẫn chưa thể giải bài toán trong trường hợp tổng quát. Bạn hãy viết chương trình giúp lớp học của Koi giải bài toán này một cách nhanh nhất nhé.

Đầu vào

Dòng đầu tiên chứa số tự nhiên \(m\) \((3 \le m \le 2000)\), điểm năng lực tối đa.

Dòng thứ hai chứa số tự nhiên \(n\) \((1 \le n \le 10^6)\), số học sinh trong lớp.

Dòng cuối cùng gồm \(n\) số tự nhiên không quá \(m\) là điểm năng lực của mỗi học sinh.

Chú ý: dữ liệu nhập-xuất lớn, bạn hãy sử dụng nhập xuất nhanh (fast io) đồng thời tránh flush khi xuất dữ liệu (VD: endl trong C++).

Đầu ra

Một dòng duy nhất là số cách chia nhóm cân bằng, lấy số dư khi chia cho \(10^9 + 7\).

Subtask

\(20\%\) số test có \(m \le 100\).

\(20\%\) số test có \(m = n\) và điểm năng lực của các sinh viên đôi một phân biệt.

Ví dụ

Đầu vào 1:

6
6
1 2 3 4 5 6

Đầu ra 1:

14

Đầu vào 2:

6
5
2 3 4 5 6

Đầu ra 2:

7