ALTPERM - Alternating Permutations

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 follows 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 separated numbers, i.e. A[1] to A[K].

Output

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

Example

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

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/

hide comments
2023-10-10 01:42:25
@zukow very easy
2019-10-18 00:54:23 :D
Phenomenal problem. Very satisfied to have finally solved it.

Last edit: 2019-10-29 21:36:27
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.