Clumsy Algorithm

　　Sorted Lists are thought beautiful while permutations are considered elegant. So what about sequence (1, 2, ... , n) ? It is the oracle from god. Now Coach Pang finds a permutation (p₁, p₂, ... , p_n) over {1, 2, ... , n} which has been shuffled by some evil guys. To show Coach Pang’s best regards to the oracle, Coach Pang decides to rearrange the sequence such that it is the same as (1, 2, 3, ... , n). The time cost of swapping p_i and p_j is 2|i- j| - 1. Of course, the minimum time cost will be paid since Coach Pang is lazy and busy. Denote the minimum time cost of the task as f(p). But Coach Pang is not good at maths. He finally works out a clumsy algorithm to get f(p) as following:

　　Coach Pang’s algorithm is clearly wrong. For example, n = 3 and (3, 2, 1) is the permutation. In this case, f(p) = 3 but g(p) = 0 + 0 + 2 = 2. The question is that how many permutations p of {1, 2, ... , n} such that f(p) = g(p). To make the problem more challenge, we also restrict the prefix of p to (a₁, a₂, ... , a_k). To sum up, you need to answer the question that how many permutations p of {1, 2, ... , n} with the fixed prefix p₁ = a₁, p₂ = a₂, ... , p_k = a_k such that f(p) = g(p). Since the answer may be very large, for convenience, you are only asked to output the remainder divided by (10⁹ + 7).

　　The first line contains a positive integer T(1 <= T <= 100), which indicates the number of test cases. T lines follow. Each line contains n, k, a₁, a₂, a₃, ... , a_k. (1 <= n <= 100, 0 <= k <= n, 1 <= a_i <= n and all a_i are distinct.)

　　For each test case, output one line “Case #x: y”, where x is the case number (starting from 1) and y is the answer to each test case.

2
3 0
5 2 1 4

Case #1: 5
Case #2: 3

Among all permutations over {1, 2, 3}, {3, 2, 1} is the only counter-example.

2013 Asia Chengdu Regional Contest