当前没有测试数据。

题目描述

A K-ary heap of size n is an array $[a_0, a_1, \ldots, a_{n - 1}]$, and for each pair of indices i and j which satisfy $0 \leq i \leq n - 1$, $K \cdot i + 1 \leq j \leq \min \lbrace K \cdot i + K, n - 1 \rbrace$, $a_j$​ is strictly greater than $a_i$​. Considering all possible K-ary heaps of size n which are also permutations obtained from 1 to n, let us write down these heaps in lexicographical order, and then label them starting from 1. For example, when n = 3, K = 2, there are two possible heaps [1, 2, 3] and [1, 3, 2], which are labeled 1 and 2 respectively. Given a K-ary heap of size n which is also a permutation obtained from 1 to n, we want you to find the label of this heap after doing the aforementioned process. As the answer can be very large, we request you to report the label modulo $(10^{9} + 7)$.

输入格式

There are multiple test cases. The first line contains an integer T ($1 \leq T \leq 20$), indicating the number of test cases. Test cases are given in the following.For each test case, the first line contains two integers n, K ($1 \leq n, K \leq 3000$).The second line contains n distinct integers $a_0$​, $a_1$, ……, $a_{n - 1}$​ ($1 \leq a_0, a_1, \ldots, a_{n - 1} \leq n$). We ensure that the given heap is a valid K-ary heap and also a permutation obtained from 1 to n.

输出格式

For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y denotes the label of the heap in this test case modulo $(10^{9} + 7)$.

样例

样例输入 1

3
3 2
1 2 3
5 2
1 2 5 4 3
7 3
1 3 5 2 4 6 7

样例输出 1

Case #1: 1
Case #2: 6
Case #3: 151