Question 1

You are given an array A of size N. Find the count of Good Subarrays in A. Since the answer may be a large return it modulo 10^9+7. A Good Subarray is one in which:- 1.) The difference between minimum and second minimum elements is not more than D. 2.) It is guaranteed that the size of the Good Subarray array is at least 2.

Input Format

The first line contains an integer N, denoting the number of elements in A. The second line contains D. The next i lines of N contains integer describing A[i]

Examples

Input 1

2 1 2 3

Output

0

Explanation

No Good Subarrays

Input 2

3 3 7 4 1

Output

3

Explanation

[0,1] , [0,2] , [1,2]

Input 3

3 1 3 7 8

Output

1

Explanation'

[1,2]