Tam giác chứa tâm đa giác

Cho một đa giác đều $n$ đỉnh, các đỉnh được đánh số từ $1$ đến $n$ theo chiều kim đồng hồ. Trong đó có $k$ đỉnh được tô màu.

Hãy cho biết có bao nhiêu cách chọn ba đỉnh khác nhau đều được tô màu sao cho tam giác xác định bởi ba đỉnh này chứa tâm của đa giác (tâm có thể nằm trên cạnh của tam giác).

Dữ liệu vào

• Dòng đầu chứa hai số nguyên dương $n,k$ ($3\le k\le n\le {10}^6$).
• Dòng thứ hai chứa $k$ số nguyên $p_1,p_2,\dots ,p_k$ ($1\le p_1<p_2<\cdots <p_k\le n$) mô tả các đỉnh được tô màu.

Dữ liệu ra

• Một số nguyên là số cách chọn ba đỉnh thoả mãn.

Ràng buộc

• $3\le k\le n\le {10}^6$.
• $1\le p_1<p_2<\cdots <p_k\le n$.

Các subtask:

• Subtask 1 (25%): $n,k\le 500$.
• Subtask 2 (25%): $n,k\le 5000$.
• Subtask 3 (25%): $k=n$.
• Subtask 4 (25%): không có ràng buộc gì thêm.

Ví dụ

Ghi chú

Số cách chọn có thể rất lớn, cần dùng kiểu số nguyên 64-bit.