小 R 喺整理一面由 $n$ 塊鏡片組成嘅摺鏡嗰陣發現：對序列 $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

樣例解釋 1

共有以下 $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$。