ALTPERM - Alternating Permutations

no tags 

You are given K indices, A[1], A[2], ... , A[K].

A[1] < A[2] < ... < A[K].

A[1] = 1 and A[K] = N.

A permutation of the numbers between 1 and N is called valid if :

The numbers in the permutation between indices A[1] and A[2] (inclusive) form an increasing sequence, the numbers in the permutation between indices A[2] and A[3] (inclusive) form a decreasing sequence, those between A[3] and A[4] (inclusive) form an increasing sequence and so on.

Count the number of valid permutations.

Input

There will be multiple test cases. The first line contains the number of test cases T.

There follow 2*T lines, 2 lines for each test case. The first line for each test case contains the numbers N and K. The second line contains K space seperated numbers, ie. A[1] to A[K].

 

Output

Output T lines, one for each test case. All answers should be output MOD 1000000007.

Example

Sample Input :
3 3 3 1 2 3 4 3 1 3 4 10 6 1 2 5 7 8 10

Sample Output : 2 3 6166


Constraints

T <= 111 2 <= N <= 20000 2 <= K <= 22

K <= N

A[1] < A[2] < ... < A[K]. A[1] = 1 and A[K] = N.



Added by:Varun Jalan
Date:2010-01-10
Time limit:2.318s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Own Problem, used for Codechef Snackdown http://www.codechef.com/