A K-ary heap of size n is an array , and for each pair of indices i and j which satisfy , , is strictly greater than .

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 .

There are multiple test cases. The first line contains an integer T (), 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 ().

The second line contains n distinct integers , , ,  (). 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 .

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

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