Mentre sistemava uno specchio pieghevole composto da $n$ pannelli, il piccolo R ha scoperto che, calcolando il resto modulo un intero $m \ge 2$ sulla sequenza $a_1, \dots, a_n$, alcuni sottointervalli diventano palindromi.

Per interi positivi $l, r, m$ ($1 \le l \le r \le n$), se $[a_l \bmod m, a_{l+1} \bmod m, \dots, a_r \bmod m]$ è una sequenza palindroma (cioè $(a_i \bmod m) = (a_{r+l-i} \bmod m)$ vale per ogni $l \le i \le r$), si definisce $f(l, r, m) = 1$; altrimenti si definisce $f(l, r, m) = 0$.

Dato un limite superiore $M$, calcola:

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

Input

La prima riga contiene due interi $n, M$ ($1 \le n \le 8000, 2 \le M \le 10^6$), che rappresentano rispettivamente la lunghezza della sequenza e il limite superiore del modulo.

La seconda riga contiene $n$ interi $a_1, a_2, \dots, a_n$ ($0 \le a_i \le M$), che rappresentano la sequenza $a$.

Output

Stampa una singola riga contenente un intero, ovvero la risposta richiesta $\sum_{1 \le l < r \le n} \sum_{2 \le m \le M} f(l, r, m)$.

La risposta potrebbe essere molto grande, quindi fai attenzione a usare interi a $64$ bit.

Esempi

Input 1

5 4
1 3 2 4 3

Output 1

3

Note

Ci sono in totale le seguenti $3$ terne $(l, r, m)$ tali che $f(l, r, m) = 1$:

• $(l, r, m) = (1, 2, 2)$: In questo caso, $[a_1 \bmod 2, a_2 \bmod 2] = [1, 1]$ è una sequenza palindroma.
• $(l, r, m) = (3, 4, 2)$: In questo caso, $[a_3 \bmod 2, a_4 \bmod 2] = [0, 0]$ è una sequenza palindroma.
• $(l, r, m) = (2, 5, 2)$: In questo caso, $[a_2 \bmod 2, a_3 \bmod 2, a_4 \bmod 2, a_5 \bmod 2] = [1, 0, 0, 1]$ è una sequenza palindroma.

Per $(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]$ non è una sequenza palindroma, pertanto $f(2, 5, 3) = 0$.