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
sdeven_0245:
20190204 04:16:15
Easy dp


i_am_hokage:
20180210 17:24:30
If it is your first problem on bracket sequence topic you may want to read about standard problems on that topic. Otherwise, It would be hard for you to determine transition between states. 

Rajivteja:
20171229 10:17:53
Solved without hint :) Motivated. Last edit: 20171229 10:18:49 

ab_hi_shek111:
20170912 23:07:26
solved and Motivated :) 

aditya9125:
20170911 22:33:34
Try iterative DP, you will definitely enjoy. 

ashishranjan28:
20170523 08:43:04
easy recursion :) 

sultania23:
20170324 08:10:46
recursion with mem... nice one.. 

ayush_1997:
20170221 19:06:27
nice problem :) 

Mayank Agarwal:
20170129 20:39:28
nice dp:) 

sushantoberoi3:
20170115 06:41:49
easy problem.. 
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 