Alternating Permutations

All submissions for this problem are available.
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 modulo 1000000007.
Constraints :
T <= 111
2 <= N <= 20000
2 <= K <= 22
K <= N
A[1] < A[2] < ... < A[K].
A[1] = 1 and A[K] = N.
Time Limit : 20 seconds.
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
Note :
For the first test case,
(1 3 2) and (2 3 1) are the valid permutations.
For the second test case,
(1 2 4 3), (1 3 4 2) and (2 3 4 1) are the valid permutations.
Author:  admin 
Tags  admin 
Date Added:  13112009 
Time Limit:  1.43 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 