Als der kleine R einen aus $n$ Spiegelflächen bestehenden Klappspiegel ordnete, stellte er fest: Wenn man die Folge $a_1, \dots, a_n$ modulo einer ganzen Zahl $m \ge 2$ betrachtet, werden einige Teilintervalle zu Palindromen.

Für positive ganze Zahlen $l, r, m$ ($1 \le l \le r \le n$) sei $f(l, r, m) = 1$, falls $[a_l \bmod m, a_{l+1} \bmod m, \dots, a_r \bmod m]$ eine Palindromfolge ist (d. h. $(a_i \bmod m) = (a_{r+l-i} \bmod m)$ gilt für alle $l \le i \le r$), und andernfalls $f(l, r, m) = 0$.

Gegeben eine obere Schranke $M$, berechne:

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

Eingabe

Die erste Zeile enthält zwei ganze Zahlen $n, M$ ($1 \le n \le 8000, 2 \le M \le 10^6$), die jeweils die Länge der Folge und die obere Schranke für den Modul angeben.

Die zweite Zeile enthält $n$ ganze Zahlen $a_1, a_2, \dots, a_n$ ($0 \le a_i \le M$), welche die Folge $a$ darstellen.

Ausgabe

Gib in einer einzigen Zeile eine ganze Zahl aus, nämlich das gesuchte Ergebnis $\sum_{1 \le l < r \le n} \sum_{2 \le m \le M} f(l, r, m)$.

Da das Ergebnis sehr groß sein kann, verwende bitte $64$-Bit-Ganzzahlen.

Beispiele

Eingabe 1

5 4
1 3 2 4 3

Ausgabe 1

3

Hinweis

Es gibt insgesamt die folgenden $3$ Tripel $(l, r, m)$, für die $f(l, r, m) = 1$ gilt:

• $(l, r, m) = (1, 2, 2)$: In diesem Fall ist $[a_1 \bmod 2, a_2 \bmod 2] = [1, 1]$ eine Palindromfolge.
• $(l, r, m) = (3, 4, 2)$: In diesem Fall ist $[a_3 \bmod 2, a_4 \bmod 2] = [0, 0]$ eine Palindromfolge.
• $(l, r, m) = (2, 5, 2)$: In diesem Fall ist $[a_2 \bmod 2, a_3 \bmod 2, a_4 \bmod 2, a_5 \bmod 2] = [1, 0, 0, 1]$ eine Palindromfolge.

Für $(l, r, m) = (2, 5, 3)$ ist $[a_2 \bmod 3, a_3 \bmod 3, a_4 \bmod 3, a_5 \bmod 3] = [0, 2, 1, 0]$ keine Palindromfolge, also gilt $f(2, 5, 3) = 0$.