LIS Number

The LIS Number of a sequence of integers $A$ is the smallest positive integer $L$ such that $A$ can be obtained by concatenating $L$ strictly increasing sequences. For example, the LIS Number of $A = \{1, 4, 4, 2, 6, 3\}$ is 4. You can get $A$ as $\{1, 4\} + \{4\} + \{2, 6\} + \{3\}$, but not with 3 or fewer sequences. The LIS Number of a strictly increasing sequence is 1.

You are given a sequence of length $N$ and an integer $K$. You want to transform the given sequence into a sequence with LIS Number $K$. The only operation you can perform is deleting 0 or more numbers from the original sequence. Count the number of ways to do this. Two ways are different if the sets of removed positions (indices) are different.

The first line contains a positive integer $t$, the number of test cases. The first line of each test case contains two integers $N$ ($1 \le N \le 50{,}000$) and $K$ ($1 \le K \le 10$). The second line contains $N$ integers of the sequence, separated by single spaces. Each integer is between 0 and 100000, inclusive.

For each test case, output the number of ways to transform the given sequence of length $N$ into a sequence with LIS Number $K$. Since the count can be very large, output it modulo $1{,}000{,}000{,}007$.