Da Lille R ordnet et foldespeil bestående av $n$ speilpaneler, oppdaget han at etter å ha tatt resten modulo et heltall $m \ge 2$ på følgen $a_1, \dots, a_n$, blir noen delintervaller til palindromer.

For positive heltall $l, r, m$ ($1 \le l \le r \le n$), hvis $[a_l \bmod m, a_{l+1} \bmod m, \dots, a_r \bmod m]$ er en palindromfølge (det vil si at $(a_i \bmod m) = (a_{r+l-i} \bmod m)$ gjelder for alle $l \le i \le r$), defineres $f(l, r, m) = 1$; ellers defineres $f(l, r, m) = 0$.

Gitt en øvre grense $M$, beregn:

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

Inndata

Den første linjen inneholder to heltall $n, M$ ($1 \le n \le 8000, 2 \le M \le 10^6$), som representerer henholdsvis lengden på følgen og den øvre grensen for modulen.

Den andre linjen inneholder $n$ heltall $a_1, a_2, \dots, a_n$ ($0 \le a_i \le M$), som representerer følgen $a$.

Utdata

Skriv ut én linje med ett enkelt heltall, det vil si det etterspurte svaret $\sum_{1 \le l < r \le n} \sum_{2 \le m \le M} f(l, r, m)$.

Svaret kan være svært stort, så pass på å bruke $64$-biters heltall.

Eksempler

Inndata 1

5 4
1 3 2 4 3

Utdata 1

3

Forklaring

Det finnes totalt følgende $3$ tripler $(l, r, m)$ slik at $f(l, r, m) = 1$:

• $(l, r, m) = (1, 2, 2)$: I dette tilfellet er $[a_1 \bmod 2, a_2 \bmod 2] = [1, 1]$ en palindromfølge.
• $(l, r, m) = (3, 4, 2)$: I dette tilfellet er $[a_3 \bmod 2, a_4 \bmod 2] = [0, 0]$ en palindromfølge.
• $(l, r, m) = (2, 5, 2)$: I dette tilfellet er $[a_2 \bmod 2, a_3 \bmod 2, a_4 \bmod 2, a_5 \bmod 2] = [1, 0, 0, 1]$ en palindromfølge.

For $(l, r, m) = (2, 5, 3)$ er $[a_2 \bmod 3, a_3 \bmod 3, a_4 \bmod 3, a_5 \bmod 3] = [0, 2, 1, 0]$ ikke en palindromfølge, så $f(2, 5, 3) = 0$.