SQRBR - Square Brackets

You are given:

  • a positive integer n,
  • an integer k, 1<=k<=n,
  • an increasing sequence of k integers 0 < s1 < s2 < ... < sk <= 2n.

What is the number of proper bracket expressions of length 2n with opening brackets appearing in positions s1, s2 ... sk?

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 s1,s2, ... sk,
  • 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 i-th line of output should contain one integer - the number of proper bracket expressions of length 2n with opening brackets appearing at positions s1, s2 ... sk.

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 

Added by:adrian
Date:2004-06-22
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:III Polish Collegiate Team Programming Contest (AMPPZ), 1998

hide comments
2019-02-04 04:16:15
Easy dp
2018-02-10 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.
2017-12-29 10:17:53 Rajivteja
Solved without hint :) Motivated.

Last edit: 2017-12-29 10:18:49
2017-09-12 23:07:26
solved and Motivated :)
2017-09-11 22:33:34
Try iterative DP, you will definitely enjoy.
2017-05-23 08:43:04
easy recursion :)
2017-03-24 08:10:46
recursion with mem... nice one..
2017-02-21 19:06:27
nice problem :)
2017-01-29 20:39:28 Mayank Agarwal
nice dp:)
2017-01-15 06:41:49
easy problem..
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.