Problem Description

给你一个正整数数组$c_1, c_2, ..., c_{n-1}$，求$n$元组$(a_1, a_2, ..., a_n)$的个数，满足$a_i$是正整数，且对于每个$i (1\leq i \leq n-1)$都有有$\max(a_i, a_{i+1}) = c_i$或者$a_i + a_{i+1} = c_i$。

由于答案很大，输出对$10^9 + 7$取模的值。

Input

第一行一个整数$T (1\leq T \leq 7)$表示数据组数。对于每组数据格式如下。

第一行一个正整数 $n(2\leq n\leq 3\times 10^3)$，接下来一行$n-1$个正整数 $c_i (2\leq c_i \leq 10^9)$。

Output

对于每组数据，一个整数表示答案。

1
5
3 4 5 6

56