Saat merapikan cermin lipat yang terdiri dari $n$ keping cermin, R Kecil menemukan bahwa setelah mengambil modulo bilangan bulat $m \ge 2$ pada barisan $a_1, \dots, a_n$, beberapa subsegmen berubah menjadi palindrom.

Untuk bilangan bulat positif $l, r, m$ ($1 \le l \le r \le n$), jika $[a_l \bmod m, a_{l+1} \bmod m, \dots, a_r \bmod m]$ adalah barisan palindrom (yaitu, $(a_i \bmod m) = (a_{r+l-i} \bmod m)$ berlaku untuk semua $l \le i \le r$), definisikan $f(l, r, m) = 1$; jika tidak, definisikan $f(l, r, m) = 0$.

Diberikan batas atas $M$, hitunglah:

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

Masukan

Baris pertama berisi dua bilangan bulat $n, M$ ($1 \le n \le 8000, 2 \le M \le 10^6$), yang masing-masing menyatakan panjang barisan dan batas atas modulus.

Baris kedua berisi $n$ bilangan bulat $a_1, a_2, \dots, a_n$ ($0 \le a_i \le M$), yang menyatakan barisan $a$.

Keluaran

Keluarkan satu baris berisi sebuah bilangan bulat, yaitu jawaban yang diminta $\sum_{1 \le l < r \le n} \sum_{2 \le m \le M} f(l, r, m)$.

Jawabannya mungkin sangat besar, harap perhatikan untuk menggunakan bilangan bulat $64$-bit.

Contoh

Masukan 1

5 4
1 3 2 4 3

Keluaran 1

3

Catatan

Terdapat $3$ tripel $(l, r, m)$ berikut sehingga $f(l, r, m) = 1$:

• $(l, r, m) = (1, 2, 2)$: Dalam hal ini, $[a_1 \bmod 2, a_2 \bmod 2] = [1, 1]$ adalah barisan palindrom.
• $(l, r, m) = (3, 4, 2)$: Dalam hal ini, $[a_3 \bmod 2, a_4 \bmod 2] = [0, 0]$ adalah barisan palindrom.
• $(l, r, m) = (2, 5, 2)$: Dalam hal ini, $[a_2 \bmod 2, a_3 \bmod 2, a_4 \bmod 2, a_5 \bmod 2] = [1, 0, 0, 1]$ adalah barisan palindrom.

Untuk $(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]$ bukan barisan palindrom, sehingga $f(2, 5, 3) = 0$.