ขณะที่เสี่ยว 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

หมายเหตุ

มีกลุ่ม $(l, r, m)$ ทั้งหมด $3$ กลุ่มดังต่อไปนี้ที่ทำให้ $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$