27217번 - Кратные отрезки 다국어

Задан массив натуральных чисел $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]$