Biswa and Restaurant Business

After huge success in Borhani business, Biswa has recently started restaurant business. He’s got the information about the numbers of customers for $N$ days, a sequence of $N$ integers $a_1, a_2, …, a_N$. He wants to calculate the popularity of his restaurant from this data. First he’ll choose a window of size $K$ ($K ≤ N$). Then for each K-sized window from the original sequence (first $K$-sized window will contain $a_1, a_2, …, a_K$, second one will contain $a_2, a_3, …, a_{K+1}$, and so on), he’ll calculate the number of all possible continuous increasing sequences in it and write them down in order. It’ll create a sequence of $N - K + 1$ integers $b_1, b_2, …, b_{N-K+1}$. Finally he’ll run the following function on the later found sequence:

Output of this function is the popularity that Biswa desires to calculate.

A sequence is increasing if for every two adjacent elements in it, the later one is greater than the previous one. A sequence containing a single element is considered to be a increasing sequence as well.

Input

First line of the test case contains a positive integer $T$ ($0 < T ≤ 10$) denoting the number of scenarios. For each scenario the first line will contain two positive integers $N$ and $K$ ($1 ≤ K ≤ N ≤ 10^5$). The second line contains a sequence $a_1, a_2, …, a_N$ ($1 ≤ a_i ≤ 10^5$), where $a_i$ equals to the number of customers on $i$-th day.

Output

For each scenario, output a single integer - the popularity in a separate line. The answer may be large so compute it modulo $10^9+7$.

Sample

Input	Output
1 4 3 1 2 3 2	16
In the sample test the sequence is: 1, 2, 3, 2 and the window size is 3. The first window will contain 1, 2, 3 and 6 possible continuous increasing sequences can be found there: $\{1, 2, 3\}$, $\{1, 2\}$, $\{2, 3\}$, $\{1\}$, $\{2\}$, $\{3\}$. Similarly the second window will contain 4 continuous increasing sequences: $\{2, 3\}$, $\{2\}$, $\{3\}$, $\{2\}$. So the sequence $b$ is: 6, 4 and if we run that function on it we’ll get 16 which is also 16 in modulo $10^9+7$.