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
2015-07-04 12:17:48 SangKuan
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.
2015-06-02 08:23:45 Amitayush Thakur
Nice DP problem. The sub-problem is difficult to think of. Also a non-DP but recursive approach can pass too.
2015-05-30 14:05:46 Deepak Singh Tomar
in some way,.. quite similar to MPILOT :)
2015-05-24 09:17:49 Naman Goyal
Why n so small? It can be increased to 500 or so and answer can be (ans mod p)
2015-03-15 23:58:03 Petar Bosnjak
@ Aradhya Makkar , easy for Croatians also :P
2015-01-04 04:09:29 (Tjandra Satria Gunawan)(曾毅昆)
Much easier than BRCKTS :p
2014-12-26 23:39:14 Rajat (1307086)
Why DP is so hard...........
2014-10-27 14:55:23 Aakash Chandrasekaran
@Aradhya Makkar I am japanese and it is easy for me :P
2014-09-15 20:13:05 Govind Lahoti
nice one :)
2014-08-28 11:46:54 Md Abdul Alim
Very Nice Problem!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.