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. 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
[Submit][Status]