Приводя в порядок складное зеркало, состоящее из $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$.