Bob's Chocolate Party

 

Bob is organizing a party where there will be ‘M’ friends of Bob attending the party. Bob has ‘N’ chocolates which he wants to distribute among his ‘M’ friends. Each chocolate has a taste value which determines how much tasty that chocolate is. But there is a condition. Since if someone got bad chocolate and someone got a good one, then the friends will be unhappy. So Bob wants to distribute chocolates in such a way that the difference between the maximum taste value and minimum taste value is less than or equal to ‘K’. Now Bob is thinking, how many possible ways are there to distribute the chocolates such that the friends remain happy.

Since the answer can be very large, you have to print the answer modulo 10^9 + 7.

For Example:

For the test case:
3 2 2
1 4 5
There is only one distribution possible i.e. [4,5] since the difference between them is 1 which is less than 2.
If we consider other distributions like [1,4], [1,5], their difference is greater than 2, so they are not a valid distribution.

Note:

Each chocolate can be given to a single friend only and each friend can get only single chocolate.

Input Format :

The first line will contain a single integer ‘T’ denoting the number of test cases. Then ‘T’ test cases follow.

The second line of each test case will contain three space-separated integers ‘N’, ‘M’, and ‘K’, denoting the number of chocolates, number of friends, and the limiting value respectively.

The next line of each test case will contain ‘N’ space-separated integers denoting the taste value of each chocolate.

Output Format :

For each test case, print a single integer denoting the number of ways Bob can distribute the chocolates.

Note :

You are not required to print anything; it has already been taken care of. Just implement the function. 

Constraints:

1 <= T <= 1000
1 <= N, K <= 10^5
1 <= M <= N
1 <= ARR[i] <= 10^5

Where ARR[i]  denotes the taste value of the ith chocolate.

It is guaranteed that the sum of N over all test cases doesn’t exceed 10^5.

Time Limit: 1 sec.   

Sample Input 1:

2
4 2 3
1 2 3 4
5 2 3
1 2 3 4 5

Sample Output 1:

6
9

Explanation For Sample Output 1:

For the first test case, all the possible distributions are 
(1,2), (1,3), (2,3), (1,4), (2,4), (3,4)

For the second test case, all the possible distributions are 
(1,2), (1,3), (1,4), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)

Sample Input 2:

2
6 1 1
1 3 2 9 5 8
6 2 1
1 3 5 11 9 7

Sample Output 2:

6
0