2015
09-18

# 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 (p1, p2, … , pn) 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 pi and pj 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 (a1, a2, … , ak). To sum up, you need to answer the question that how many permutations p of {1, 2, … , n} with the fixed prefix p1 = a1, p2 = a2, … , pk = ak 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 (109 + 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, a1, a2, a3, … , ak. (1 <= n <= 100, 0 <= k <= n, 1 <= ai <= n and all ai are distinct.)

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, a1, a2, a3, … , ak. (1 <= n <= 100, 0 <= k <= n, 1 <= ai <= n and all ai are distinct.)

2
3 0
5 2 1 4

Case #1: 5
Case #2: 3

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


1. 在人心善恶面前，其它都不算什么！放开了其实跟你也没多大关系，有的只是你所谓的利益体得失多少而已。人心的善恶区更重要，哪怕你一直都看不清别人的善恶。

2. 在人心善恶面前，其它都不算什么！放开了其实跟你也没多大关系，有的只是你所谓的利益体得失多少而已。人心的善恶区更重要，哪怕你一直都看不清别人的善恶。

3. 在人心善恶面前，其它都不算什么！放开了其实跟你也没多大关系，有的只是你所谓的利益体得失多少而已。人心的善恶区更重要，哪怕你一直都看不清别人的善恶。

4. 在人心善恶面前，其它都不算什么！放开了其实跟你也没多大关系，有的只是你所谓的利益体得失多少而已。人心的善恶区更重要，哪怕你一直都看不清别人的善恶。

5. 在人心善恶面前，其它都不算什么！放开了其实跟你也没多大关系，有的只是你所谓的利益体得失多少而已。人心的善恶区更重要，哪怕你一直都看不清别人的善恶。

6. 在人心善恶面前，其它都不算什么！放开了其实跟你也没多大关系，有的只是你所谓的利益体得失多少而已。人心的善恶区更重要，哪怕你一直都看不清别人的善恶。

7. 在人心善恶面前，其它都不算什么！放开了其实跟你也没多大关系，有的只是你所谓的利益体得失多少而已。人心的善恶区更重要，哪怕你一直都看不清别人的善恶。

8. 在人心善恶面前，其它都不算什么！放开了其实跟你也没多大关系，有的只是你所谓的利益体得失多少而已。人心的善恶区更重要，哪怕你一直都看不清别人的善恶。

9. 在人心善恶面前，其它都不算什么！放开了其实跟你也没多大关系，有的只是你所谓的利益体得失多少而已。人心的善恶区更重要，哪怕你一直都看不清别人的善恶。

10. 在人心善恶面前，其它都不算什么！放开了其实跟你也没多大关系，有的只是你所谓的利益体得失多少而已。人心的善恶区更重要，哪怕你一直都看不清别人的善恶。

11. 在人心善恶面前，其它都不算什么！放开了其实跟你也没多大关系，有的只是你所谓的利益体得失多少而已。人心的善恶区更重要，哪怕你一直都看不清别人的善恶。

12. 在人心善恶面前，其它都不算什么！放开了其实跟你也没多大关系，有的只是你所谓的利益体得失多少而已。人心的善恶区更重要，哪怕你一直都看不清别人的善恶。

13. 在人心善恶面前，其它都不算什么！放开了其实跟你也没多大关系，有的只是你所谓的利益体得失多少而已。人心的善恶区更重要，哪怕你一直都看不清别人的善恶。