أثناء ترتيب مرآة قابلة للطي تتكون من $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$.