LIS 넘버

정수로 이루어진 수열 $A$의 LIS 넘버는 엄격하게 증가하는 수열 $L$개를 이어 붙여 $A$를 만들 수 있는 가장 작은 양의 정수 $L$이다. 예를 들어 $A = \{1, 4, 4, 2, 6, 3\}$의 LIS 넘버는 4이다. $\{1, 4\} + \{4\} + \{2, 6\} + \{3\}$으로 $A$를 얻을 수 있지만, 3개 이하의 수열로는 만들 수 없다. 엄격하게 증가하는 수열의 LIS 넘버는 1이다.

길이가 $N$인 수열과 정수 $K$가 주어진다. 주어진 수열을 LIS 넘버가 $K$인 수열로 바꾸려 한다. 할 수 있는 연산은 원래 수열에서 0개 이상의 수를 삭제하는 것뿐이다. 이 방법의 수를 세어라. 삭제한 위치(인덱스)의 집합이 다르면 서로 다른 방법으로 본다.

첫 줄에 테스트 케이스의 개수를 나타내는 양의 정수 $t$가 주어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $N$ ($1 \le N \le 50{,}000$)과 $K$ ($1 \le K \le 10$)가 주어진다. 둘째 줄에는 수열의 정수 $N$개가 공백 한 칸으로 구분되어 주어진다. 각 정수는 0 이상 100000 이하이다.

각 테스트 케이스에 대해, 길이 $N$의 주어진 수열을 LIS 넘버가 $K$인 수열로 바꾸는 방법의 수를 출력한다. 수가 매우 커질 수 있으므로 $1{,}000{,}000{,}007$로 나눈 나머지를 출력한다.