Problem 1343 --Mathematician Long Aotian## 1343: 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. Define\( f(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

## HINT

## Source

[Submit][Status]