Þegar Litli R var að raða saman fellispegli sem samanstendur af $n$ spegilplötum uppgötvaði hann að eftir að hafa tekið afganginn modulo heiltölu $m \ge 2$ á rununni $a_1, \dots, a_n$, verða sum hlutbil að samhverfum (palindrom).

Fyrir jákvæðar heiltölur $l, r, m$ ($1 \le l \le r \le n$), ef $[a_l \bmod m, a_{l+1} \bmod m, \dots, a_r \bmod m]$ er samhverf runa (það er, $(a_i \bmod m) = (a_{r+l-i} \bmod m)$ gildir fyrir öll $l \le i \le r$), þá skilgreinum við $f(l, r, m) = 1$, en annars skilgreinum við $f(l, r, m) = 0$.

Með gefið efra mark $M$, vinsamlegast reiknið:

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

Inntak

Fyrsta línan inniheldur tvær heiltölur $n, M$ ($1 \le n \le 8000, 2 \le M \le 10^6$), sem tákna annars vegar lengd rununnar og hins vegar efra mark deilistölunnar.

Önnur línan inniheldur $n$ heiltölur $a_1, a_2, \dots, a_n$ ($0 \le a_i \le M$), sem tákna rununa $a$.

Úttak

Skrifið út eina heiltölu á einni línu, sem er umbeðna svarið $\sum_{1 \le l < r \le n} \sum_{2 \le m \le M} f(l, r, m)$.

Svarið getur verið mjög stórt, svo gætið þess að nota $64$-bita heiltölur.

Dæmi

Inntak 1

5 4
1 3 2 4 3

Úttak 1

3

Athugasemd

Alls eru eftirfarandi $3$ þrenndir $(l, r, m)$ þannig að $f(l, r, m) = 1$:

• $(l, r, m) = (1, 2, 2)$: Í þessu tilfelli er $[a_1 \bmod 2, a_2 \bmod 2] = [1, 1]$ samhverf runa.
• $(l, r, m) = (3, 4, 2)$: Í þessu tilfelli er $[a_3 \bmod 2, a_4 \bmod 2] = [0, 0]$ samhverf runa.
• $(l, r, m) = (2, 5, 2)$: Í þessu tilfelli er $[a_2 \bmod 2, a_3 \bmod 2, a_4 \bmod 2, a_5 \bmod 2] = [1, 0, 0, 1]$ samhverf runa.

Fyrir $(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]$ ekki samhverf runa, þannig að $f(2, 5, 3) = 0$.