Khi đang sắp xếp một chiếc gương gấp gồm $n$ mảnh gương, Tiểu R phát hiện ra rằng: sau khi lấy phần dư của dãy số $a_1, \dots, a_n$ theo một số nguyên $m \ge 2$, một số đoạn con sẽ trở thành dãy đối xứng.

Với các số nguyên dương $l, r, m$ ($1 \le l \le r \le n$), nếu $[a_l \bmod m, a_{l+1} \bmod m, \dots, a_r \bmod m]$ là một dãy đối xứng (tức là $(a_i \bmod m) = (a_{r+l-i} \bmod m)$ đúng với mọi $l \le i \le r$), ta định nghĩa $f(l, r, m) = 1$, ngược lại ta định nghĩa $f(l, r, m) = 0$.

Cho trước cận trên $M$, hãy tính:

$$\sum_{1 \le l < r \le n} \sum_{2 \le m \le M} f(l, r, m)$$

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n, M$ ($1 \le n \le 8000, 2 \le M \le 10^6$), lần lượt biểu thị độ dài của dãy số và cận trên của số chia dư.

Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($0 \le a_i \le M$), biểu thị dãy số $a$.

Dữ liệu ra

In ra một dòng chứa một số nguyên duy nhất là đáp án cần tìm $\sum_{1 \le l < r \le n} \sum_{2 \le m \le M} f(l, r, m)$.

Đáp án có thể rất lớn, hãy lưu ý sử dụng kiểu số nguyên $64$-bit.

Ví dụ

Dữ liệu vào 1

5 4
1 3 2 4 3

Dữ liệu ra 1

3

Ghi chú

Có tất cả $3$ bộ $(l, r, m)$ sau đây thỏa mãn $f(l, r, m) = 1$:

• $(l, r, m) = (1, 2, 2)$: Khi đó $[a_1 \bmod 2, a_2 \bmod 2] = [1, 1]$ là dãy đối xứng.
• $(l, r, m) = (3, 4, 2)$: Khi đó $[a_3 \bmod 2, a_4 \bmod 2] = [0, 0]$ là dãy đối xứng.
• $(l, r, m) = (2, 5, 2)$: Khi đó $[a_2 \bmod 2, a_3 \bmod 2, a_4 \bmod 2, a_5 \bmod 2] = [1, 0, 0, 1]$ là dãy đối xứng.

Đối với $(l, r, m) = (2, 5, 3)$, $[a_2 \bmod 3, a_3 \bmod 3, a_4 \bmod 3, a_5 \bmod 3] = [0, 2, 1, 0]$ không phải là dãy đối xứng, do đó $f(2, 5, 3) = 0$.