| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 256 MB | 0 | 0 | 0 | 0.000% |
A $d$-ary heap of size $n$ is an array $a_1, a_2, \ldots, a_n$ where for each pair of indices $i$ and $j$ such that $1 \le i \le n$, $1 \le j \le n$ and $(i - 1) \cdot d + 2 \le j \le i \cdot d + 1$, the strict inequality $a_j > a_i$ holds. For example, for a ternary ($d = 3$) heap of size $8$, the required inequalities are: $a_2 > a_1$, $a_3 > a_1$, $a_4 > a_1$, $a_5 > a_2$, $a_6 > a_2$, $a_7 > a_2$, and $a_8 > a_3$.
Consider all $d$-ary heaps of size $n$ which also happen to be permutations of numbers from $1$ to $n$. Let us write them all down in lexicographical order comparing permutations as sequences of numbers. After that, we enumerate the heaps in the resulting ordered list starting from $1$.
You are given a $d$-ary heap of size $n$ which is also a permutation. Your task is to find the number of this heap in the ordered list constructed above. As the answer can be very large, compute it modulo $(10^9 + 7)$.
The first line of input contains a positive integer $T$: the number of test cases. The test cases follow.
Each test case is given on two lines. The first of these lines contains two integers $n$ and $d$ ($1 \le n \le 3000$, $1 \le d \le 3000$). The second line contains $n$ integers describing the permutation. Each integer from $1$ to $n$ occurs on that line exactly once. The given permutation is also a $d$-ary heap.
The sum of all values of $n$ in the input does not exceed $3000$.
For each test case, print the $1$-based number of the given sequence in the lexicographically ordered list of $d$-ary heaps which are also permutations, modulo $(10^9 + 7)$.
2 5 2 1 3 2 4 5 5 3 1 4 3 2 5
7 12