Blocks divisible by k

Problem

Count the blocks of consecutive items whose sum is divisible by k. Items can be negative.

Example

Input

6 5
4 5 0 -2 -3 1

Output

Seven blocks have a sum that is a multiple of 5.

Try the problem first. Open one hint at a time.

Hint 1

Two prefix sums with the same remainder have a multiple of k between them.

Hint 2

Count prefix remainders. In Python, % with a positive k never returns a negative number.

Write your Python code, run it on the examples and submit it to hidden tests.