У Анны Николаевны есть
N ящиков с конфетами. В
i-м ящике лежит
Ai количество конфет. Анна Николаевна достает конфеты из нескольких последовательных коробок и равномерно раздает их
M детям. Найдите количество пар (
l,
r), удовлетворяющих следующим условиям:
-
l и
r целые числа и удовлетворяют условию
1<=l<=r<=N;
-
Al + Al+1 + ...
+ Ar делится на
M.
Входные данные
Программа получает на вход две строки. Первая строка содержит два целых числа
N (1<=N<=10
5) и
M (2<=M<=10
9). Вторая строка содержит
N чисел
Ai (1<=A
i<=10
9, 1<=i<=N).
Выходные данные
Выведите количество пар (
l,
r), удовлетворяющих условиям. Обратите внимание, что число может не соответствовать 32-битному целочисленному типу.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3 2
4 1 5 |
3 |
| 2 |
13 17
29 7 5 7 9 51 7 13 8 55 42 9 81 |
6 |