【题目描述】

有一个$n$行的残缺棋盘，从上到下行号依次为$1$到$n$。第$i$行有紧靠左边的连续$a_i$个格子，且对于任意$1\le i <n$，有$a_i \ge a_{i+1}$。

例如，当$n=3$，每行分别有$3,2,2$个格子时，棋盘如下所示：

现有一个棋子在左上角的格子里，其余格子均为空白。每次操作可以选择棋盘内的一个棋子，将其分裂成两个，其中一个往右移动一格，另一个往下移动一格。棋子可能会移动到棋盘外，一个格子里可以同时容纳任意多个棋子。

请你根据给定的棋盘，计算至少在多少次操作之后，棋盘内没有任何棋子。

【输入格式】

第一行一个整数$t$，表示有$t$组数据。

对于每组数据，第一行一个整数$n$，表示棋盘的行数。

第二行$n$个空格隔开的整数，表示每行的格子数量。

【输出格式】

$t$行，每行一个整数，表示题目所求的操作次数，答案对$10^9+7$取余数。

2
2
3 2
3
3 2 2

6
10

1
10
15 14 12 10 8 7 6 4 0 0

3872

【样例解释】

样例1的第一组数据中：

第1次对(1,1)操作后，棋盘内的棋子为(2,1) (1,2)。

第2次对(2,1)操作后，棋盘内的棋子为(1,2) (2,2)。

第3次对(2,2)操作后，棋盘内的棋子为(1,2)。

第4次对(1,2)操作后，棋盘内的棋子为(1,3) (2,2)。

第5次对(2,2)操作后，棋盘内的棋子为(1,3)。

第6次对(1,3)操作后，棋盘内没有棋子。

【数据规模与约定】

对于$20\%$的数据，保证$t=1, 1\le n\le 3, 0\le a_i\le 3$。

对于$50\%$的数据，保证$t\le 3$。

对于$100\%$的数据，保证$1\le t\le 2000,1\le n\le 1000, 0\le a_i\le 1000$。