Järjestellessään $n$ peilipaneelista koostuvaa taittopeiliä Pikku R huomasi, että kun lukujonon $a_1, \dots, a_n$ luvuista otetaan jakojäännös kokonaisluvulla $m \ge 2$, jotkin osavälit muuttuvat palindromeiksi.

Positiivisille kokonaisluvuille $l, r, m$ ($1 \le l \le r \le n$), jos $[a_l \bmod m, a_{l+1} \bmod m, \dots, a_r \bmod m]$ on palindromijono (eli $(a_i \bmod m) = (a_{r+l-i} \bmod m)$ pätee kaikilla $l \le i \le r$), määritellään $f(l, r, m) = 1$, ja muussa tapauksessa määritellään $f(l, r, m) = 0$.

Annettuna yläraja $M$, laske:

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

Syöte

Ensimmäinen rivi sisältää kaksi kokonaislukua $n, M$ ($1 \le n \le 8000, 2 \le M \le 10^6$), jotka kuvaavat lukujonon pituutta ja jakajan ylärajaa.

Toinen rivi sisältää $n$ kokonaislukua $a_1, a_2, \dots, a_n$ ($0 \le a_i \le M$), jotka kuvaavat lukujonon $a$.

Tuloste

Tulosta yhdelle riville yksi kokonaisluku, eli kysytty vastaus $\sum_{1 \le l < r \le n} \sum_{2 \le m \le M} f(l, r, m)$.

Vastaus voi olla hyvin suuri, joten muista käyttää $64$-bittisiä kokonaislukuja.

Esimerkit

Syöte 1

5 4
1 3 2 4 3

Tuloste 1

3

Huomautus

On yhteensä seuraavat $3$ kolmikkoa $(l, r, m)$, joilla $f(l, r, m) = 1$:

• $(l, r, m) = (1, 2, 2)$: Tällöin $[a_1 \bmod 2, a_2 \bmod 2] = [1, 1]$ on palindromijono.
• $(l, r, m) = (3, 4, 2)$: Tällöin $[a_3 \bmod 2, a_4 \bmod 2] = [0, 0]$ on palindromijono.
• $(l, r, m) = (2, 5, 2)$: Tällöin $[a_2 \bmod 2, a_3 \bmod 2, a_4 \bmod 2, a_5 \bmod 2] = [1, 0, 0, 1]$ on palindromijono.

Kolmikolle $(l, r, m) = (2, 5, 3)$ jono $[a_2 \bmod 3, a_3 \bmod 3, a_4 \bmod 3, a_5 \bmod 3] = [0, 2, 1, 0]$ ei ole palindromijono, joten $f(2, 5, 3) = 0$.