Mientras organizaba un espejo plegable compuesto por $n$ paneles de espejo, el pequeño R descubrió que, al tomar módulo un entero $m \ge 2$ sobre la secuencia $a_1, \dots, a_n$, algunos subsegmentos se convierten en palíndromos.

Para enteros positivos $l, r, m$ ($1 \le l \le r \le n$), si $[a_l \bmod m, a_{l+1} \bmod m, \dots, a_r \bmod m]$ es una secuencia palíndroma (es decir, $(a_i \bmod m) = (a_{r+l-i} \bmod m)$ se cumple para todo $l \le i \le r$), se define $f(l, r, m) = 1$; en caso contrario, se define $f(l, r, m) = 0$.

Dada una cota superior $M$, calcula:

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

Entrada

La primera línea contiene dos enteros $n, M$ ($1 \le n \le 8000, 2 \le M \le 10^6$), que representan respectivamente la longitud de la secuencia y la cota superior del módulo.

La segunda línea contiene $n$ enteros $a_1, a_2, \dots, a_n$ ($0 \le a_i \le M$), que representan la secuencia $a$.

Salida

Imprime una línea con un único entero, la respuesta solicitada $\sum_{1 \le l < r \le n} \sum_{2 \le m \le M} f(l, r, m)$.

La respuesta puede ser muy grande, por lo que se recomienda utilizar enteros de $64$ bits.

Ejemplos

Entrada 1

5 4
1 3 2 4 3

Salida 1

3

Nota

Hay en total las siguientes $3$ ternas $(l, r, m)$ tales que $f(l, r, m) = 1$:

• $(l, r, m) = (1, 2, 2)$: En este caso, $[a_1 \bmod 2, a_2 \bmod 2] = [1, 1]$ es una secuencia palíndroma.
• $(l, r, m) = (3, 4, 2)$: En este caso, $[a_3 \bmod 2, a_4 \bmod 2] = [0, 0]$ es una secuencia palíndroma.
• $(l, r, m) = (2, 5, 2)$: En este caso, $[a_2 \bmod 2, a_3 \bmod 2, a_4 \bmod 2, a_5 \bmod 2] = [1, 0, 0, 1]$ es una secuencia palíndroma.

Para $(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]$ no es una secuencia palíndroma, por lo tanto $f(2, 5, 3) = 0$.