Подотрезки с суммой, кратной k

Даны список из $n$ чисел и число $k$. Сколько существует непустых кусков из подряд идущих элементов, сумма которых делится нацело на $k$?

В первой строке числа $n$ от $1$ до $2 \cdot 10^5$ и $k$ от $1$ до $10^5$ через пробел. Во второй — $n$ целых чисел от $0$ до $10^9$.

Одно число.

Сумма куска делится на $k$ тогда, когда префиксы на его концах дают одинаковый остаток. Считайте, сколько раз встретился каждый остаток.