652. Pastries in Hawen

0

Medium

In the town of Hawen, there are N shops that sell Pastries. Each shop sells pastries with different taste levels. Dhruv wants to have pastries with a total taste value of K. However, he can only have pastries from consecutive shops, meaning he cannot skip any shops in between. For example, if there are 5 shops numbered 1, 2, 3, 4, 5, then eating from 1-3-4 would not be a valid choice, but eating from 1-2-3 or 3-4-5 or 1-2 or 2-3-4-5 would be valid. Can you determine the number of different groups of shops Dhruv could have pastries from?

Input Format

The first line contains two space-separated integers N and K.
The next line contains N space-separated integers, representing the taste levels at each shop.

Output Format

Print the number of different groups of shops Dhruv could have pastries from.

Example

Input

3 3
1 2 3

Output

2

Constraints

1 <= N <= 10^5
|A_i| < 10^3
|K| < 10^7

Loading...

View Submissions

Console