Алекс записал результаты n последовательных измерений. Результат каждого — целое неотрицательное число. Для отчёта он может выбрать любой непустой непрерывный фрагмент журнала.
Фрагмент считается согласованным, если сумма его чисел делится на K без остатка. Посчитайте количество согласованных фрагментов. Фрагменты с разными границами считаются различными, даже если числа в них совпадают. Нулевая сумма делится на K.
Входные данные
Первая строка содержит целые числа n и K (1 ≤ n ≤ 200 000, 1 ≤ K ≤ 109). Вторая строка содержит n чисел aᵢ (0 ≤ aᵢ ≤ 109).
Выходные данные
Выведите количество согласованных непустых фрагментов.
Пояснения к примерам
Пример 1. Подходят фрагменты [1,2], [1,3], [1,5], [3,3], [3,5], [4,5], [2,4]; в скобках указаны номера границ.
Пример 2. Подходят все шесть непустых фрагментов.
| № | Входные данные | Выходные данные |
|
1
|
5 3
1 2 3 1 2
|
7
|
|
2
|
3 7
0 0 0
|
6
|