Кратные отрезки

Задан массив натуральных чисел $A = \[a\_1, a\_2, \ldots, a\_n]$. Отрезком массива $A$ с $l$ по $r$ будем называть массив $\[a\_l, a\_{l+1}, \ldots, a\_r]$.

Для заданного массива $A$ и числа $k$ требуется найти количество пар $(l, r)$, таких что $l \le r$ и сумма чисел на отрезке массива $A$ с $l$ по $r$ делится на $k$ без остатка.

На первой строке ввода заданы целые числа $n$ --- число элементов массива $A$ и $k$ ($1 \le n \le 200\\,000$, $2 \le k \le 10^9$).

На второй строке заданы целые числа $a\_1, a\_2, \ldots, a\_n$ --- элементы массива $A$ ($1 \le a\_i \le 10^9$).

Выведите одно число: количество пар $(l, r)$, таких что $l \le r$, и сумма чисел на отрезке массива $A$ с $l$ по $r$ делится на $k$ без остатка.

В примере подходят следующие отрезки:

• $l = 1$, $r = 3$, отрезок $\[1, 2, 3]$
• $l = 1$, $r = 4$, отрезок $\[1, 2, 3, 4]$
• $l = 2$, $r = 2$, отрезок $\[2]$
• $l = 2$, $r = 5$, отрезок $\[2, 3, 4, 5]$
• $l = 3$, $r = 5$, отрезок $\[3, 4, 5]$
• $l = 4$, $r = 4$, отрезок $\[4]$