Traversal

In this city, all the parks are labelled with integers from $1$ to $n$ except for $k$ integers: $a_1$, $a_2$, $...$, $a_k$. Different parks have different integers as identities. With the development of transport, more and more express lanes appear in this city. Two parks have an express lane between them if the difference between their identities is 1 or p or p+2.

When Mr. Wu first came to this city, he decided to visit all the parks by taking some circular tourist routes for several days. A circular tourist route is a loop route with at least three parks. For each two adjacent parks in this circular order, there exists an express lane between them.

Mr. Wu planed to visit each park only one time. The problem is: how many different plans are there to design the route. Two plans are different if and only if they have some different circular routes. Note that the translation and inversion provide the same circular tourist routes as the original route.

There are multiple test cases (no more than $20$ test cases), and the first line contains an integer $t$, meaning the total number of test cases.

For each test case, the first line contains two integers $n$ and $p$, where $1 \le n \le 100, 2 \le p \le 9$. The second line contains $k+1$ integers. The first integer is $k$, where $k < n$. And $k$ integers follow, $a_1$, $a_2$, $...$, $a_k$.

For each test case, print one line containing the total number of plans modulo $10007$.

4
6 3
0
6 2
0
5 3
1 5
6 3
3 2 5 3

Case #1: 6
Case #2: 10
Case #3: 1
Case #4: 0

All the plans in the first test case are:
(1, 2, 3, 4, 5, 6)
(1, 2, 3, 6, 5, 4)
(1, 2, 5, 4, 3, 6)
(1, 2, 5, 6, 3, 4)
(1, 4, 3, 2, 5, 6)
(1, 4, 5, 2, 3, 6)
All the plans in the second test case are:
(1, 2, 3, 4, 6, 5)
(1, 2, 4, 6, 5, 3)
(1, 2, 6, 4, 3, 5)
(1, 2, 6, 4, 5, 3)
(1, 2, 6, 5, 4, 3)
(1, 3, 2, 4, 6, 5)
(1, 3, 2, 6, 4, 5)
(1, 3, 4, 2, 6, 5)
(1, 2, 3), (4, 5, 6)
(1, 3, 5), (2, 4, 6)

2015 ACM/ICPC Asia Regional Shenyang Online