Stretches with an exact total

Problem

A bank statement lists daily changes, which can be negative. Count the non-empty consecutive stretches of days whose changes add up to exactly k.

Example 1

Input

5 3
1 2 1 2 1

Output

Four stretches add to 3.

Example 2

Input

3 0
1 -1 0

Output

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

Hint 1

Let prefix be the running total. A stretch adds to k when two prefix totals differ by k.

Hint 2

Keep a dictionary that counts each prefix total seen so far, starting with {0: 1}.

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