You are given an array of N elements and an integer K . Let f(i,j) denote sum of min( K, j-i+1 ) greatest elements of the subarray from i to j. You need to compute sum of f(i,j) over all subarrays .

codechef2.py

def sub_lists(my_list):
	subs = [[]]
	for i in range(len(my_list)):
		n = i+1
		while n <= len(my_list):
			sub = my_list[i:n]
			subs.append(sub)
			n += 1
	
	return subs
t=int(raw_input())

result=[]
for i in range(t):
    summed=[]
    k=raw_input()
    k=k.split()
    for p in range(len(k)):
        k[p]=int(k[p])
        
    l=raw_input()
    l=l.split(" ")
    for p in range(len(l)):
        l[p]=int(l[p])
   
    subsl=sub_lists(l)
    for j in subsl:
        flag=0
        while len(j)> 0 and flag != k[1]:
            flag+=1
            summed.append(max(j))
            j.remove(max(j))
          
    result.append(sum(summed))
if len(result)==2:
    print result[0]
    print result[1]
else:
    print result[0]


            
            
            

Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains 2 integers N , K where N denotes the size of the array and K denotes the number of greatest elements of each subarray to be considered .

The second line contains N space-separated integers A1, A2, ..., AN denoting the elements of the array .

Output
For each test case, output a single line containing the answer for that test case modulo 10^9 + 7

Constraints
1 ≤ T ≤ 2
1 ≤ N ≤ 100000
1 ≤ K ≤ 100
1 ≤ Ai ≤ 10^9

Example
Input:
1
4 2
1 2 3 4

Output:
44