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\)