Chef has an array A = (A1, A2, ..., AN), which has N integers in it initially. Chef found that for i ≥ 1, if Ai > 0, Ai+1 > 0, and Ai+2 exists, then he can decrease both Ai, and Ai+1 by one and increase Ai+2 by one. If Ai+2 doesn't exist, but Ai > 0, and Ai+1 > 0, then he can decrease both Ai, and Ai+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 109+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 in A.
- The second line contains N space-separated integers: A1, A2, ... , AN. 

-----Output-----
For each test case, output answer modulo 109+7 in a single line. 

-----Constraints-----
- 1 ≤ T ≤ 5
- 1 ≤ N ≤ 50
- 0 ≤ Ai ≤ 50

-----Subtasks-----
- Subtask 1 (20 points) : 1 ≤ N ≤ 8, 0 ≤ Ai ≤ 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.

Difficulty: interview

Starter code:

Solutions:
def fun(a,cur,n,cnt):
    if cur>=n-1:
        return
    for i in range(cur,n-1):
        if i<n-2:
            if a[i]>0 and a[i+1]>0:
                a[i]-=1
                a[i+1]-=1
                a[i+2]+=1
                cnt[0]=(cnt[0]+1)%1000000007
                fun(a,i,n,cnt)
                a[i]+=1
                a[i+1]+=1
                a[i+2]-=1
        else:
            if a[i]>0 and a[i+1]>0:
                a[i]-=1
                a[i+1]-=1
                a.append(1)
                cnt[0]=(cnt[0]+1)%1000000007
                fun(a,i,n+1,cnt)
                a[i]+=1
                a[i+1]+=1
                a.pop()
tc=int(input())
for case in range(tc):
    n=int(input())
    a=list(map(int,input().split()))
    cnt=[1]
    fun(a,0,n,cnt)
    print(cnt[0]%1000000007)
    


def fun(a,cur,n,cnt):
    if cur>=n-1:
        return
    for i in range(cur,n-1):
        if i<n-2:
            if a[i]>0 and a[i+1]>0:
                a[i]-=1
                a[i+1]-=1
                a[i+2]+=1
                cnt[0]+=1
                fun(a,i,n,cnt)
                a[i]+=1
                a[i+1]+=1
                a[i+2]-=1
        else:
            if a[i]>0 and a[i+1]>0:
                a[i]-=1
                a[i+1]-=1
                a.append(1)
                cnt[0]+=1
                fun(a,i,n+1,cnt)
                a[i]+=1
                a[i+1]+=1
                a.pop()
tc=int(input())
for case in range(tc):
    n=int(input())
    a=list(map(int,input().split()))
    cnt=[1]
    fun(a,0,n,cnt)
    print(cnt[0])
    


from sys import stdin
 
mod = 10**9 + 7
max_val = 135

cache2 = [[0]*max_val for _ in range(max_val)]
done = [[False]*max_val for _ in range(max_val)]
def f2(x, y):
	if done[x][y]:
		res = cache2[x][y]
	elif x == 0 or y == 0:
		res = 1
		cache2[x][y] = res
		done[x][y] = True
	elif x > y:
		res = f2(y, y)
		cache2[x][y] = res
		done[x][y] = True
	else:
		res = sum(f2(y-i, i) for i in range(x+1))
		cache2[x][y] = res
		done[x][y] = True
	return res % mod
 
def solve():
	n = int(stdin.readline().strip())
	a = list(map(int, stdin.readline().strip().split()))
	
	cache = [[[0]*max_val for _ in range(max_val)] for _ in range(51)]
	done = [[[False]*max_val for _ in range(max_val)] for _ in range(51)]
	def f(i, x, y):
		if done[i][x][y]:
			res = cache[i][x][y]
		elif i == n-1:
			res = 1
			cache[i][x][y] = res
			done[i][x][y] = True
		elif i == n-2:
			res = f2(x, y)
			cache[i][x][y] = res
			done[i][x][y] = True
		elif x == 0:
			res = f(i+1, y, a[i+2])
			cache[i][x][y] = res
			done[i][x][y] = True
		else:
			k = min(x, y)
			res = 0
			for z in range(k+1):
				res += f(i+1, y-z, a[i+2]+z)
				res %= mod
			cache[i][x][y] = res
			done[i][x][y] = True	
		return res % mod
	
	print(f(0, a[0], a[1]) if n >= 2 else 1)
 
t = int(stdin.readline().strip())
for _ in range(t):
	solve()

from sys import stdin
 
mod = 10**9 + 7
	
cache2 = [[0]*501 for _ in range(501)]
done = [[False]*501 for _ in range(501)]
def f2(x, y):
	if done[x][y]:
		res = cache2[x][y]
	elif x == 0 or y == 0:
		res = 1
		cache2[x][y] = res
		done[x][y] = True
	elif x > y:
		res = f2(y, y)
		cache2[x][y] = res
		done[x][y] = True
	else:
		res = sum(f2(y-i, i) for i in range(x+1))
		cache2[x][y] = res
		done[x][y] = True
	return res % mod
 
def solve():
	n = int(stdin.readline().strip())
	a = list(map(int, stdin.readline().strip().split()))
	
	cache = [[[0]*501 for _ in range(501)] for _ in range(51)]
	done = [[[False]*501 for _ in range(501)] for _ in range(51)]
	def f(i, x, y):
		if done[i][x][y]:
			res = cache[i][x][y]
		elif i == n-1:
			res = 1
			cache[i][x][y] = res
			done[i][x][y] = True
		elif i == n-2:
			res = f2(x, y)
			cache[i][x][y] = res
			done[i][x][y] = True
		elif x == 0:
			res = f(i+1, y, a[i+2])
			cache[i][x][y] = res
			done[i][x][y] = True
		else:
			k = min(x, y)
			res = 0
			for z in range(k+1):
				res += f(i+1, y-z, a[i+2]+z)
				res %= mod
			cache[i][x][y] = res
			done[i][x][y] = True	
		return res % mod
	
	print(f(0, a[0], a[1]) if n >= 2 else 1)
 
t = int(stdin.readline().strip())
for _ in range(t):
	solve()

import pdb

           
def gen_sig(arr):
    sig = ';'.join(map(str,arr))
    return sig

def solve(arr,cache):
    l = len(arr)
    cnt =0
    for i in range(l-1):
        if arr[i] >0 and arr[i+1]>0:
            if i == l-2:
                arr[i]-=1
                arr[i+1]-=1
                arr.append(1)
                sig = gen_sig(arr)
                if (sig in cache) == False:
                    cache[sig]=1
                    ret = solve(arr,cache)
                    if ret >=0:
                        cnt+=ret+1
                arr.pop(-1)
                arr[i+1]+=1
                arr[i]+=1
            else:
                arr[i]-=1
                arr[i+1]-=1
                arr[i+2]+=1
                sig = gen_sig(arr)
                if (sig in cache) == False:
                    cache[sig]=1
                    ret = solve(arr,cache)
                    if ret >=0:
                        cnt+=ret+1
                arr[i]+=1
                arr[i+1]+=1
                arr[i+2]-=1
    #cache[gen_sig(arr)] = cnt
    return cnt

def __starting_point():
    T = int(input())
    for t  in range(T):
        n = int(input())
        arr = list(map(int, input().split()))
        cache = {}
        cache[gen_sig(arr)]=1
        solve(arr,cache)
        print(len(cache))

__starting_point()