You are given a rectangle **1*N**, where its **1*1**
squares can be painted as white or black. So, one can build a "code" of this
rectangle - this will be a sequence of numbers, the number of consequent black
squares from left to right.

For example, the code of this rectangle is **2 3 2 8 1**.
However, the number of white squares is not counted anywhere (but two groups of
black squares must be separated by at least one white square). That is why,
there are a few rectangles which can satisfy the same code. For example, the
following rectangle satisfies the given code as well.

The problem is to calculate the number of rectangles, which can satisfy the given code.

**Input**

There can be multiple
test cases. The first line of the input gives you the number of test cases **T
(1< T < 20)**. In the next T lines you would have the input for each of
the test cases. Each test case consists of N the length of a rectangle **(1
<= N <= 200)**. Then K - the number of numbers in a code **(0 <= K
<= (N+1)/2)**. Then K numbers, which represent the code itself.

**Output**

The output consists of
one number - the number of rectangles, which can satisfy the given code. You can
assume that the output will always fit in a **50 digit** integer.

Sample Input |
Sample Output |

3 4 0 5 2 1 2 4 2 2 2 |
1 3 0 |

Problem translation & initial checking: Dmytro Chernysh

Special thanks to Monirul Hasan