小 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]$ が回文列である場合（すなわち、すべての $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)$$

入力

1 行目には 2 つの整数 $n, M$ ($1 \le n \le 8000, 2 \le M \le 10^6$) が与えられ、それぞれ数列の長さと法の上界を表します。

2 行目には $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)$ を表す 1 つの整数を 1 行に出力してください。

答えは非常に大きくなる可能性があるため、$64$ ビット整数を使用することに注意してください。

入出力例

入力 1

5 4
1 3 2 4 3

出力 1

3

注記

$f(l, r, m) = 1$ となる組 $(l, r, m)$ は以下の $3$ 組あります：

• $(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$ です。