Sum of Numbers 2

Interview

Time limit0.5sMemory limit128 MB

Summary

Given N positive integers and a target M, count contiguous subarrays whose sum equals M.

Level: Easy3 of 10
Topics: Two pointers, Prefix sum, Array
Solved: No attempts yet

Problem

You are given a sequence A[1], A[2], ..., A[N] of N positive integers. Count the number of pairs (i, j) such that the sum of the contiguous segment A[i], A[i+1], ..., A[j] is exactly M.

Input

The first line contains N (1 <= N <= 10,000) and M (1 <= M <= 300,000,000). The second line contains A[1], A[2], ..., A[N], separated by spaces. Each A[x] is a positive integer not greater than 30,000.

Output

Print the number of contiguous segments whose sum is M.

Examples2

Example 1
Input
```
4 2
1 1 1 1
```
Expected output
```
3
```
Example 2
Input
```
10 5
1 2 3 4 2 5 3 1 1 2
```
Expected output
```
3
```