$n$ айна бөлігінен тұратын жиналмалы айнаны ретке келтіріп жатқанда, Кішкентай R $a_1, \dots, a_n$ тізбегін $m \ge 2$ бүтін санына бөлгендегі қалдықты алғаннан кейін кейбір кесінділер палиндромға айналатынын байқады.

Оң бүтін $l, r, m$ ($1 \le l \le r \le n$) сандары үшін, егер $[a_l \bmod m, a_{l+1} \bmod m, \dots, a_r \bmod m]$ палиндром тізбек болса (яғни барлық $l \le i \le r$ үшін $(a_i \bmod m) = (a_{r+l-i} \bmod m)$ орындалса), онда $f(l, r, m) = 1$ деп, ал кері жағдайда $f(l, r, m) = 0$ деп анықтаймыз.

Берілген жоғарғы шек $M$ үшін келесі өрнекті есептеңіз:

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

Кіріс деректер

Бірінші жолда сәйкесінше тізбектің ұзындығын және модульдің жоғарғы шегін білдіретін екі бүтін сан $n, M$ ($1 \le n \le 8000, 2 \le M \le 10^6$) берілген.

Екінші жолда $a$ тізбегін білдіретін $n$ бүтін сан $a_1, a_2, \dots, a_n$ ($0 \le a_i \le M$) берілген.

Шығыс деректер

Бір жолға бір бүтін санды — ізделінді $\sum_{1 \le l < r \le n} \sum_{2 \le m \le M} f(l, r, m)$ жауабын шығарыңыз.

Жауап өте үлкен болуы мүмкін, сондықтан $64$-биттік бүтін сандарды қолдануды ескеріңіз.

Мысалдар

Кіріс деректер 1

5 4
1 3 2 4 3

Шығыс деректер 1

3

Ескертпе

Барлығы $f(l, r, m) = 1$ болатын келесі $3$ үштік $(l, r, m)$ бар:

• $(l, r, m) = (1, 2, 2)$: Бұл жағдайда $[a_1 \bmod 2, a_2 \bmod 2] = [1, 1]$ палиндром тізбек болады.
• $(l, r, m) = (3, 4, 2)$: Бұл жағдайда $[a_3 \bmod 2, a_4 \bmod 2] = [0, 0]$ палиндром тізбек болады.
• $(l, r, m) = (2, 5, 2)$: Бұл жағдайда $[a_2 \bmod 2, a_3 \bmod 2, a_4 \bmod 2, a_5 \bmod 2] = [1, 0, 0, 1]$ палиндром тізбек болады.

Ал $(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]$ палиндром тізбек емес, сондықтан $f(2, 5, 3) = 0$.