Description

A国马上就要和B国打仗了。为了有效的防止B国对A国领海发动奇袭，A国军事部长决定在海岸上布置海防大炮，每个海防大炮都威力巨大，但价格不菲，B国听闻这个消息马上研发了一个专门克制海防大炮的新型大炮，A国听到听到这个武器之后，就邀请了你，希望你能合理布局每个海防大炮的位置，以尽量减少每次新型大炮发射所摧毁的海炮数量。

A国军事部长给了你一个A国的海岸线地图，你可以简单的把他看成一个不那么规则的网格图，一种海岸线长度为 $9$ 的地图大概样子可以如下：

其中$len[i]$表示海岸线从左往右第i个位置往上延申最远能有多少格

新型大炮虽然厉害，但它的攻击范围却只能是一条直线，它每次发射都可以随意选择某一行(列)发射一枚炮弹，这枚炮弹会沿直线飞行来摧毁这一行(列)上所有格子里的海防炮。

对于每个格子你都可以放置 多个 海防炮，当然也可以不放。因为每个海防炮都造价不菲，所以国防部长希望你能找出 所有的布阵方案 ，使得无论新型大炮怎么发射，他最多只能一次性摧毁$2$或以下数量的海防炮。

在这里我只需要你输出方案的总个数即可。这个方案数可能会非常大，所以需要你对答案和1e9+7取模 。

Input Format

题目包含多组样例，在第一行输入一个整数$T$ $(1≤T≤10)$。

对于每组样例，在第一行输入整数$n$($1≤n≤200$)表示，海岸线的总长度。

在第二行输入$n$个有空格隔开的整数$len[i]$ $(1≤len[i]≤200)$，含义请看题目描述。

Output Format

对于每个样例在一行输出一个整数，表示所有合法布局的方案数。

2
1
1
2
1 2

3
14