【题目描述】

有 N 堆石子排成一行，第 i 堆有 a_i 个石子。

你可以进行以下操作：

如果两个相邻的石子堆的石子个数相差恰好为 1，你可以从数量较多的石子堆中取走 1 个放到数量较少的石子堆里。

你可以操作任意次。每次操作后，你都可以得到一个石子堆序列。

问：你最多可以得到多少个不同的石子堆序列(包含初始序列）？

答案可能很大，你只需要输出答案 mod (10^9+7) 。

注：两个石子堆序列被认为是相同的，当且仅当对于任意 i （1 ≤ i ≤ N），第 i 堆石子在两个序列中具有相同数量的石子。

【输入格式】

第一行：一个整数 T，表示数据组数。

每组数据占两行：

• 第一行：一个整数 N
• 第二行：N 个整数 a_i

输入保证所有组数据的 N 之和不超过 5000。

【输出格式】

共 T 行，每组数据的答案占一行。

【样例输入】

3
4
1 1 1 2
5
1 3 5 2 4
6
2 2 1 1 3 3

【样例输出】

4
1
15

【部分样例解释】

此处仅解释第 1 组数据，4 个可能的序列为：1 1 1 2; 1 1 2 1; 1 2 1 1; 2 1 1 1.

【数据规模】

全部测试点满足：1 ≤ N ≤ 5000, 1 ≤ a_i ≤ 2^30。

测试点 1-3： N ≤ 10。

测试点 4： 1 ≤ a_i ≤ 3。

测试点 5-7： |a_i-i| ≤ 1。

测试点 8-10： N ≤ 100，1 ≤ a_i ≤ 4。

测试点 11-13： N ≤ 100。

测试点 14-17： N ≤ 1000。

测试点 18-20 没有额外限制。