题目描述

如同往常一样，奶牛 Bessie 正在 Farmer John 的牛棚里制造麻烦。FJ 有 $N$（$1 \leq N \leq 5000$）堆草堆。对于每个 $i \in [1,N]$，第 $i$ 堆草堆有 $h_i$（$1 \leq h_i \leq 10^9$）的草。Bessie 不想让任何的草倒下来，所以她唯一可以执行的操作为：

如果两个相邻的草堆的高度相差恰好为 $1$，她可以将较高的草堆中最上方的草移到较低的草堆之上。

执行有限多次上述操作后，可以得到多少种不同的高度序列，对 $10^9+7$ 取模？两个高度序列被认为是相同的，如果对于所有 $i$，第 $i$ 堆草堆在两者中具有相同数量的草。

输入格式

输入的第一行包含 $T$，为独立的子测试用例的数量，必须全部回答正确才能通过整个测试用例。

每个子测试用例包含 $N$，以及一个 $N$ 个高度的序列。输入保证所有子测试用例的 $N$ 之和不超过 $5000$。

输出格式

输出 $T$ 行，每行输出一个子测试用例的答案。

样例

输入

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

输出

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 \leq 10$
• 测试点 $4$ 满足对于所有 $i$，有 $1 \leq h_i \leq 3$
• 测试点 $5$-$7$ 满足对于所有 $i$，有 $|h_i - i| \leq 1$
• 测试点 $8$-$10$ 满足对于所有 $i$，有 $1 \leq h_i \leq 4$，且 $N \leq 100$
• 测试点 $11$-$13$ 满足 $N \leq 100$
• 测试点 $14$-$17$ 满足 $N \leq 1000$
• 测试点 $18$-$21$ 没有额外限制