奶牛 Bessie 又在 Farmer John 的谷仓里捣乱了。FJ 有 $N$ ($1\leq N \leq 5000$) 堆干草捆。对于每个 $i\in [1,N]$，第 $i$ 堆有 $h_i$ ($1\le h_i\le 10^9$) 个干草捆。Bessie 不希望任何干草捆掉落，因此她唯一能执行的操作如下：
- 如果两堆相邻的干草堆高度恰好相差 1，她可以将较高那一堆顶部的干草捆移动到较低的那一堆。
在执行上述操作有限次后，可以得到多少种不同的配置？请将结果对 $10^9+7$ 取模。如果对于所有 $i$，两种配置中第 $i$ 堆的干草捆数量相同，则认为这两种配置是相同的。
输入格式
第一行包含 $T$ ($1\le T\le 10$)，表示独立测试用例的数量，必须全部解决才能正确处理一个输入。
每个测试用例包含 $N$，随后是 $N$ 个高度组成的序列。保证所有测试用例的 $N$ 之和不超过 $5000$。
输出格式
请输出 $T$ 行，每行对应一个测试用例的结果。
样例
输入 1
7
4
2 2 2 3
4
3 3 1 2
4
5 3 4 2
6
3 3 1 1 2 2
6
1 3 3 4 1 2
6
4 1 2 3 5 4
10
1 5 6 6 6 4 2 3 2 5输出 1
4
4
5
15
9
8
19说明
对于第一个测试用例，四种可能的配置为：
$$(2,2,2,3), (2,2,3,2), (2,3,2,2), (3,2,2,2)。$$
对于第二个测试用例，四种可能的配置为：
$$(2,3,3,1),(3,2,3,1),(3,3,2,1), (3,3,1,2)。$$
子任务
- 输入 1-3 满足 $N\le 10$。
- 输入 4 满足对于所有 $i$，$1\le h_i\le 3$。
- 输入 5-7 满足对于所有 $i$，$|h_i-i|\le 1$。
- 输入 8-10 满足对于所有 $i$，$1\le h_i\le 4$ 且 $N\le 100$。
- 输入 11-13 满足 $N\le 100$。
- 输入 14-17 满足 $N\le 1000$。
- 输入 18-21 满足无额外约束。
题目来源：Daniel Zhang