SQRBR  Square Brackets
You are given:
 a positive integer n,
 an integer k, 1<=k<=n,
 an increasing sequence of k integers 0 < s_{1} < s_{2} < ... < s_{k} <= 2n.
What is the number of proper bracket expressions of length 2n with opening brackets appearing in positions s_{1}, s_{2},...,s_{k}?
Illustration
Several proper bracket expressions:
[[]][[[]][]] [[[][]]][][[]]
An improper bracket expression:
[[[][]]][]][[]]
There is exactly one proper expression of length 8 with opening brackets in positions 2, 5 and 7.
Task
Write a program which for each data set from a sequence of several data sets:
 reads integers n, k and an increasing sequence of k integers from input,
 computes the number of proper bracket expressions of length 2n with opening brackets appearing at positions s_{1},s_{2},...,s_{k},
 writes the result to output.
Input
The first line of the input file contains one integer d, 1 <= d <= 10, which is the number of data sets. The data sets follow. Each data set occupies two lines of the input file. The first line contains two integers n and k separated by single space, 1 <= n <= 19, 1 <= k <= n. The second line contains an increasing sequence of k integers from the interval [1;2n] separated by single spaces.
Output
The ith line of output should contain one integer  the number of proper bracket expressions of length 2n with opening brackets appearing at positions s_{1}, s_{2},...,s_{k}.
Example
Sample input: 5 1 1 1 1 1 2 2 1 1 3 1 2 4 2 5 7 Sample output: 1 0 2 3 2
hide comments
:.Mohib.::
20151110 08:45:48
A very nice question....!! 

Anoop Narang:
20151014 10:00:18
how come answer for last 2nd case is 3. I can only count 2 ways. 

priyank:
20151007 20:17:01
nice dp :) My 150th 

xceptor:
20150912 21:04:45
Nice Problem ! 

SangKuan:
20150704 12:17:48
not my first dp,but hard for me.because there is a assume...the input s1,s2,s3..sn is the pos of [.so sad,my 100th.it is not ac by myself. 

Amitayush Thakur:
20150602 08:23:45
Nice DP problem. The subproblem is difficult to think of. Also a nonDP but recursive approach can pass too. 

Deepak Singh Tomar:
20150530 14:05:46
in some way,.. quite similar to MPILOT :) 

Naman Goyal:
20150524 09:17:49
Why n so small? It can be increased to 500 or so and answer can be (ans mod p) 

Petar Bosnjak:
20150315 23:58:03
@ Aradhya Makkar , easy for Croatians also :P 

(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20150104 04:09:29
Much easier than BRCKTS :p 
Added by:  adrian 
Date:  20040622 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  III Polish Collegiate Team Programming Contest (AMPPZ), 1998 