You are given an array $A$ of $n$ integers and an integer $k$. From the array $A$, a new array $B$ of size $n \times k$ is obtained by concatenating the array $A$, $k$ times. For example, if $A=[2,3,2]$ and $k=2$, then $B=[2,3,2,2,3,2]$.

In a step, one of the elements is randomly removed from $B$. For example, if $B=[2,3,2]$ then after one step, B could be $[2,3]$ or $[2,2]$ or $[3,2]$. Let $E[i]$ be the expected value of the number of inversions in $B$ after $i$ steps. An inversion is defined as the number of pairs of indices $i,j$ such that $i<j$ and $B[i]>B[j]$. Find the value of $\sum\limits_{i=0}^{n\times k} \ E[i]$ modulo $10^9+7$. It's guaranteed that the answer can be represented as rational fraction $\frac{P}{Q}$ where $\gcd(P,Q)=1$ , so print the value $P . Q^{−1} \mod 10^9+7$.

There are multiple test cases in a single input file.

Input format

• First line: An integer $t$ denoting the number of test cases.
• First line of $i^{th}$ test case: Two integers $n_i$ and $k_i$ followed by a line consisting of $n_i$ integers of the array $A$

Output format

For each test case, print the answer in a new line.

Constraints

$1\le t \le 10^5$

$1\le\sum\limits_{i=1}^t \ n_i\le3*10^5$

$1\le n_i\times k_i\le 10^9$

$1\le A[i]\le n$