Description

As usual, Bessie the cow is causing trouble in Farmer John's barn. FJ has $N$ stacks of haybales. For each $i\in [1,N]$, the $i$th stackhas $h_i$ haybales. Bessie does not want any haybales tofall, so the only operation she can perform is as follows:

• If two adjacent stacks' heights differ by exactly one, she can move the tophaybale of the taller stack to the shorter stack.

How many configurations are obtainable after performing the above operationfinitely many times, modulo $10^9+7$? Two configurations are considered the sameif, for all $i$, the $i$th stack has the same number of haybales in both.

• $1\leq N \leq 5000$
• $1\le h_i\le 10^9$

Input Format

The first line contains $T$ ($1\le T\le 10$), the number of independent testcases, all of which must be solved to solve one input correctly.

Each test case consists of $N$, and then a sequence of $N$ heights. It isguaranteed that the sum of $N$ over all test cases does not exceed $5000$.

Output Format

Please output $T$ lines, one for each test case.

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

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

Scoring

• Inputs 1-3 satisfy $N\le 10$.
• Input 4 satisfies $1\le h_i\le 3$ for all $i$.
• Inputs 5-7 satisfy $|h_i-i|\le 1$ for all $i$.
• Inputs 8-10 satisfy $1\le h_i\le 4$ for all $i$ and $N\le 100$.
• Inputs 11-13 satisfy $N\le 100$.
• Inputs 14-17 satisfy $N\le 1000$.
• Inputs 18-21 satisfy no additional constraints.

Problem Credit

Problem credits: Daniel Zhang