Впорядковуючи складане дзеркало, що складається з $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]$ є паліндромною послідовністю (тобто $(a_i \bmod m) = (a_{r+l-i} \bmod m)$ виконується для всіх $l \le i \le r$), визначимо $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$), які позначають довжину послідовності та верхню межу модуля відповідно.

Другий рядок містить $n$ цілих чисел $a_1, a_2, \dots, a_n$ ($0 \le a_i \le M$), які задають послідовність $a$.

Вихідні дані

Виведіть в одному рядку одне ціле число — шукану відповідь $\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

Примітка

Загалом існує $3$ такі трійки $(l, r, m)$, для яких $f(l, r, m) = 1$:

• $(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$.