Description

Input

The first line of each test contains the integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test.

The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 5000$) — the number of tiles in a row and the length of the block.

The second line of each test case contains $n$ integers $c_1, c_2, c_3, \dots, c_n$ ($1 \le c_i \le n$) — tile colors.

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $25 \cdot 10^6$.

Output

Print $t$ numbers, each of which is the answer to the corresponding test case — the number of nice paths of maximum length modulo $10^9 + 7$.

5
5 2
1 2 3 4 5
7 2
1 3 1 3 3 1 3
11 4
1 1 1 1 1 1 1 1 1 1 1
5 2
1 1 2 2 2
5 1
1 2 3 4 5
 
 
 
 
 
 

1
4
165
3
1

Note

In the first sample, it is impossible to make a nice path with a length greater than $0$.

In the second sample, we are interested in the following paths:

• $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$
• $2 \rightarrow 4 \rightarrow 5 \rightarrow 7$
• $1 \rightarrow 3 \rightarrow 5 \rightarrow 7$
• $1 \rightarrow 3 \rightarrow 4 \rightarrow 7$

In the third example, any path of length $8$ is nice.