We have a sequence of N squares drawn side by side
side. Each square has an annotated natural number
inside him. Given the sequence of N squares and a value
K, how many distinct rectangles are there whose sum of
numbers within the rectangle is exactly equal to K? Per
For example, the figure shows a sequence of N = 10 squares
for which there are 5 rectangles whose sum of numbers
is equal to K = 4.
2 0 1 1 0 0 8 4 1 3
2 0 1 1 0 0 8 4 1 3
2 0 1 1 0 0 8 4 1 3
2 0 1 1 0 0 8 4 1 3
2 0 1 1 0 0 8 4 1 3
Input
The first line of the input contains two integers N and K representing the number of squares in the
sequence and the value of the desired sum. The second line of the entry contains N natural numbers Xi,
to 1 i N, indicating the sequence of numbers noted within the squares.
Output
Your program should print a line containing an integer representing how many rectangles
exist in the sequence whose sum is equal to K.
Restrictions
1 N 500000 (5105)
0 K 106
0 Xi 100 for 1 i N
Punctuation information
In a set of test cases totaling 10 points, N 500
In a set of test cases adding 20 points, N 104
In a set of test cases summing 30 points, K> 0 and Xi> 0 for 1 i N
In a set of test cases totaling 40 points, no further restrictions (note that
for this subtask the output integer may not fit in 32 bits.)
Examples
Input example 1
10 4
2 0 1 1 0 0 8 4 1 3
Output example 1
5
Example of input 2
15 0
0 0 0 0 0 5 12 0 1 0 0 0 51 0 0
Output example 2
25
side. Each square has an annotated natural number
inside him. Given the sequence of N squares and a value
K, how many distinct rectangles are there whose sum of
numbers within the rectangle is exactly equal to K? Per
For example, the figure shows a sequence of N = 10 squares
for which there are 5 rectangles whose sum of numbers
is equal to K = 4.
2 0 1 1 0 0 8 4 1 3
2 0 1 1 0 0 8 4 1 3
2 0 1 1 0 0 8 4 1 3
2 0 1 1 0 0 8 4 1 3
2 0 1 1 0 0 8 4 1 3
Input
The first line of the input contains two integers N and K representing the number of squares in the
sequence and the value of the desired sum. The second line of the entry contains N natural numbers Xi,
to 1 i N, indicating the sequence of numbers noted within the squares.
Output
Your program should print a line containing an integer representing how many rectangles
exist in the sequence whose sum is equal to K.
Restrictions
1 N 500000 (5105)
0 K 106
0 Xi 100 for 1 i N
Punctuation information
In a set of test cases totaling 10 points, N 500
In a set of test cases adding 20 points, N 104
In a set of test cases summing 30 points, K> 0 and Xi> 0 for 1 i N
In a set of test cases totaling 40 points, no further restrictions (note that
for this subtask the output integer may not fit in 32 bits.)
Examples
Input example 1
10 4
2 0 1 1 0 0 8 4 1 3
Output example 1
5
Example of input 2
15 0
0 0 0 0 0 5 12 0 1 0 0 0 51 0 0
Output example 2
25