Chef has an array A = (A₁, A₂, ..., A_N), which has N integers in it initially. Chef found that for i ≥ 1, if A_i > 0, A_i+1 > 0, and A_i+2 exists, then he can decrease both A_i, andA_i+1 by one and increase A_i+2 by one. If A_i+2 doesn‘t exist, but A_i > 0, and A_i+1 > 0, then he can decrease both A_i, and A_i+1 (which will be the currently last two elements of the array) by one and add a new element at the end, whose value is 1.

Now Chef wants to know the number of different arrays that he can make from A using this operation as many times as he wishes. Help him find this, and because the answer could be very large, he is fine with you reporting the answer modulo 10⁹+7.

Two arrays are same if they have the same number of elements and if each corresponding element is the same. For example arrays (2,1,1) and (1,1,2) are different.

Input

• The first line of the input contains a single integer T denoting the number of test cases.
• The first line contains a single integer N denoting the initial number of elements inA.
• The second line contains N space-separated integers: A₁, A₂, ... , A_N.

Output

For each test case, output answer modulo 10⁹+7 in a single line.

Constraints

• 1 ≤ T ≤ 5
• 1 ≤ N ≤ 50
• 0 ≤ A_i ≤ 50

Subtasks

• Subtask 1 (20 points) : 1 ≤ N ≤ 8, 0 ≤ A_i ≤ 4
• Subtask 2 (80 points) : Original constraints

Example

Input:
3
3
2 3 1
2
2 2
3
1 2 3

Output:
9
4
9

Explanation

Example case 1.

We‘ll list the various single steps that you can take (ie. in one single usage of the operation):

• (2, 3, 1) → (2, 2, 0, 1)
• (2, 2, 0, 1) → (1, 1, 1, 1)
• (1, 1, 1, 1) → (1, 1, 0, 0, 1)
• (1, 1, 0, 0, 1) → (0, 0, 1, 0, 1)
• (1, 1, 1, 1) → (1, 0, 0, 2)
• (1, 1, 1, 1) → (0, 0, 2, 1)
• (2, 3, 1) → (1, 2, 2)
• (1, 2, 2) → (0, 1, 3)

So all the arrays you can possibly get are:

(2, 3, 1), (2, 2, 0, 1), (1, 1, 1, 1), (1, 1, 0, 0, 1), (0, 0, 1, 0, 1), (1, 0, 0, 2), (0, 0, 2, 1), (1, 2, 2), and (0, 1, 3)

Since there are 9 different arrays that you can reach, the answer is 9.

——————————————————————————————————

这道题明显每次只关系到相邻两位QAQ

所以我们可以从左到右dp

f【i】【j】【k】表示i-1位已经处理并且i值为i进位为k 所以i+1的值就是v【i+1】+k

然后我们就枚举操作次数x（x<=v【i+1】+k&&x<=j)推出i+1的情况就好辣

易得i个数比n打不了多少 我们求出最大的 i 答案就是f【i】【0】【0】辣

而j也不会超过一个值 这里我带了个200 至于k同理咯QAQ

codechef AUG17 T5 Chef And Fibonacci Array