Subarrays with a given sum

Problem

Count the contiguous subarrays of a list of integers whose sum equals k. Numbers may be negative.

Input: Line 1: the numbers. Line 2: k.
Output: One integer.
Constraints: 1 ≤ length ≤ 100000
-1000 ≤ each number ≤ 1000
-1000000000 ≤ k ≤ 1000000000

Example 1

Input

1 2 3 -3 3
3

Output

[1,2], [3], [1,2,3,-3], [3,-3,3], [3].

Example 2

Input

1 1 1
2

Output

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

Hint 1

A subarray sum is a difference of two prefix sums.

Hint 2

Keep a dictionary counting how often each prefix sum occurred.

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