En rangeant un miroir pliant composé de $n$ facettes, Petit R a découvert qu'après avoir pris le reste modulo un entier $m \ge 2$ sur la séquence $a_1, \dots, a_n$, certains sous-segments deviennent des palindromes.
Pour des entiers strictement positifs $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]$ est une séquence palindrome (c'est-à-dire que $(a_i \bmod m) = (a_{r+l-i} \bmod m)$ est vérifié pour tout $l \le i \le r$), on définit $f(l, r, m) = 1$, sinon on définit $f(l, r, m) = 0$.
Étant donné une borne supérieure $M$, veuillez calculer :
$$\sum_{1 \le l < r \le n} \sum_{2 \le m \le M} f(l, r, m)$$
Entrée
La première ligne contient deux entiers $n, M$ ($1 \le n \le 8000, 2 \le M \le 10^6$), représentant respectivement la longueur de la séquence et la borne supérieure du modulo.
La deuxième ligne contient $n$ entiers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le M$), représentant la séquence $a$.
Sortie
Affichez un seul entier sur une ligne, représentant la réponse demandée $\sum_{1 \le l < r \le n} \sum_{2 \le m \le M} f(l, r, m)$.
La réponse pouvant être très grande, veillez à utiliser des entiers sur $64$ bits.
Exemples
Entrée 1
5 4 1 3 2 4 3
Sortie 1
3
Remarque
Il y a au total les $3$ triplets $(l, r, m)$ suivants tels que $f(l, r, m) = 1$ :
- $(l, r, m) = (1, 2, 2)$ : Dans ce cas, $[a_1 \bmod 2, a_2 \bmod 2] = [1, 1]$ est une séquence palindrome.
- $(l, r, m) = (3, 4, 2)$ : Dans ce cas, $[a_3 \bmod 2, a_4 \bmod 2] = [0, 0]$ est une séquence palindrome.
- $(l, r, m) = (2, 5, 2)$ : Dans ce cas, $[a_2 \bmod 2, a_3 \bmod 2, a_4 \bmod 2, a_5 \bmod 2] = [1, 0, 0, 1]$ est une séquence palindrome.
Pour $(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]$ n'est pas une séquence palindrome, donc $f(2, 5, 3) = 0$.