Problem G: Mathematician Long Aotian

## Problem G: Mathematician Long Aotian

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 324  Solved: 49
[Submit][Status][Web Board]

## Description

Long Aotian is a famous mathematician. He has a sequence {$$a_i$$} of length n and the sequence {$$a_i$$} is a permutation of [1,...,n]. One day he comes up with a question. Definef(l,r,k) = \left\{\begin{aligned} & the \ product \ of \ the \ largest \ and \ k-th \ largest \ element \ in \ the \ subinterval \{ a_l, a_{l+1},...,a_{r-1},a_r \} \ when \ r-l+1>=k \\ & 0 \ when \ r-l+1<k \end{aligned} \right..Now given k, what the value of $$\sum_{l=1}^{n}\sum_{r=l}^{n}f(l,r,k)$$  mod ($$10^9+7$$)is. Long Aotian thinks the question is too easy to do, so he asks you to solve it.

## Input

The first line of input contains an integer T(1<=T<=10) which is the total number of test cases.
For each test case,there are only two integers n,k(1<=n<=100000, 1<=k<=min(80,n)) on first line,and the second line consists of n integers which means the sequence {$$a_i$$} ( $$a_i$$ <= 1000000)

## Output

For each test case,output an integer, which means the answer of the equation.

## Sample Input

1
5 2
1 2 3 4 5

## Sample Output

130

[Submit][Status]