大小为 $n$ 的 $d$-叉堆是一个数组 $a_1, a_2, \dots, 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$。例如，对于大小为 $8$ 的三叉堆（$d = 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$ 且恰好是 $1$ 到 $n$ 的排列的 $d$-叉堆。我们将它们全部按字典序（将排列视为数字序列进行比较）写下来。然后，我们从 $1$ 开始对结果有序列表中的堆进行编号。

给定一个大小为 $n$ 且为排列的 $d$-叉堆。你的任务是找出该堆在上述构造的有序列表中的编号。由于答案可能非常大，请计算其对 $(10^9 + 7)$ 取模的结果。

输入格式

输入的第一行包含一个正整数 $T$：测试用例的数量。接下来是各测试用例。

每个测试用例由两行给出。第一行包含两个整数 $n$ 和 $d$（$1 \le n \le 3000$，$1 \le d \le 3000$）。第二行包含描述该排列的 $n$ 个整数。$1$ 到 $n$ 之间的每个整数在该行中恰好出现一次。给定的排列也是一个 $d$-叉堆。

输入中所有 $n$ 的总和不超过 $3000$。

输出格式

对于每个测试用例，输出给定序列在所有作为排列的 $d$-叉堆的字典序列表中的 $1$-基编号，结果对 $(10^9 + 7)$ 取模。

样例

样例输入 1

2
5 2
1 3 2 4 5
5 3
1 4 3 2 5

样例输出 1

7
12