## 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
```

hide comments
 Deepak Singh Tomar: 2015-05-30 14:05:46 in some way,.. quite similar to MPILOT :) Naman Goyal: 2015-05-24 09:17:49 Why n so small? It can be increased to 500 or so and answer can be (ans mod p) Petar Bosnjak: 2015-03-15 23:58:03 @ Aradhya Makkar , easy for Croatians also :P (Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2015-01-04 04:09:29 Much easier than BRCKTS :p Rajat (1307086): 2014-12-26 23:39:14 Why DP is so hard........... Aakash Chandrasekaran: 2014-10-27 14:55:23 @Aradhya Makkar I am japanese and it is easy for me :P Govind Lahoti: 2014-09-15 20:13:05 nice one :) Md Abdul Alim: 2014-08-28 11:46:54 Very Nice Problem!! AmirShams: 2014-08-04 16:07:23 nice one Prakhar Gupta: 2014-07-02 07:38:42 can someone explain 4th test case??

 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