בזמן שסידר מראה מתקפלת המורכבת מ-$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$.