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]$