Dam and Pumps

Time Limit: 3 Seconds    Memory Limit: 131072 KB

There is a dam with n pumps aligned in a row to disgorge the water behind the dam. These pumps are numbered 1 to n from left to right. Initially some of the pumps are switched on. A pump can be switched on (the pump should be switched off at that moment) if there is at least one adjacent pump which is already switched on. A worker wants to switch all the pumps on. He knows the initial state of pumps and he's wondering how many different ways there exist to switch all the pumps on. Please find the required number of ways modulo 10⁹ + 7.

Input

The first line of the input, contains a single integer t, the number of test cases, followed by the input data for each test case. In the second line there are two integers n and m, where n is the number of pumps in the sequence and m is the number of pumps which are initially switched on, (1 <= n <= 1000, 1 <= m <= n). The third line contains m distinct integers, each between 1 to n inclusively, denoting the indices of pumps which are initially switched on.

Output

For each test case, print a single line containing the number of different possible ways to switch on all the pumps modulo ( 10⁹ + 7).

Sample Input

3
3 2
1 3
5 1
3
10 3
8 2 5

Sample Output

1
6
2520

Submit