힙

크기가 $n$인 $d$-ary 힙은 배열 $a_1, a_2, \ldots, a_n$이며, $1 \le i \le n$, $1 \le j \le n$, $(i - 1) \cdot d + 2 \le j \le i \cdot d + 1$을 만족하는 모든 인덱스 쌍 $(i, j)$에 대해 $a_j > a_i$가 엄격하게 성립한다. 예를 들어 $d = 3$이고 크기가 $8$인 3진 힙에서는 $a_2 > a_1$, $a_3 > a_1$, $a_4 > a_1$, $a_5 > a_2$, $a_6 > a_2$, $a_7 > a_2$, $a_8 > a_3$이 성립해야 한다. 크기가 $n$인 $d$-ary 힙 중 $1$부터 $n$까지의 수를 원소로 하는 순열인 것을 모두 고른다. 이들을 수열로 보고 사전식 순서로 나열한 뒤 $1$번부터 번호를 매긴다. 주어지는 것은 크기가 $n$인 $d$-ary 힙이면서 순열이기도 한 배열이다. 이 배열이 위 목록에서 몇 번째인지 구하라. 답이 매우 클 수 있으므로 $(10^9 + 7)$로 나눈 나머지를 구한다.

첫 줄에 테스트 케이스의 개수 $T$가 양의 정수로 주어진다. 각 테스트 케이스는 두 줄로 주어진다. 첫 줄에는 두 정수 $n$과 $d$ ($1 \le n \le 3000$, $1 \le d \le 3000$)가 주어진다. 둘째 줄에는 순열을 나타내는 $n$개의 정수가 주어진다. 이 줄에는 $1$부터 $n$까지의 각 정수가 정확히 한 번씩 나타난다. 주어진 순열은 $d$-ary 힙이기도 하다. 모든 테스트 케이스의 $n$을 합하면 $3000$을 넘지 않는다.

각 테스트 케이스마다, 주어진 수열이 $d$-ary 힙이면서 순열인 수열들의 사전식 목록에서 몇 번째인지를 $1$부터 세어 출력한다. 답은 $(10^9 + 7)$로 나눈 나머지로 출력한다.