Coach Ankit is forming a team for the Annual Inter Galactic Relay Race. He has N students that train under him and he knows their strengths. The strength of a student is represented by a positive integer.
The coach has to form a team of K students. The strength of a team is defined by the strength of the weakest student in the team. Now he wants to know the sum of strengths of all the teams of size K that can be formed modulo 1000000007. Please help him.
Input
The first line contains the number of test cases T.
Each case begins with a line containing integers N and K. The next line contains N space-separated numbers which describe the strengths of the students.
Output
For test case output a single integer, the answer as described in the problem statement.
Constraints:
1<=T<=100
1<=N<=100000
1<=K<=N
0<=Strength of each student<=2000000000
Strength of all the students are different.
For first test case: 5+4=9, as team can only consist of 1 student. For second test case: min(1,0) + min(1,2) + min(0,2) = 0+1+0 =1
