Problem Description

As usual, the cow Bessie is causing trouble in Farmer John’s barn. FJ has $N$ ($1 \le N \le 5000$) haybale stacks. For each $i \in [1,N]$, the $i$-th stack contains $h_i$ ($1 \le h_i \le 10^9$) haybales. Bessie does not want any haybales to fall over, so the only operation she can perform is:

If the heights of two adjacent stacks differ by exactly $1$, she can move the top haybale from the taller stack onto the shorter stack.

After performing the above operation a finite number of times, how many different height sequences can be obtained, modulo $10^9+7$? Two height sequences are considered the same if, for all $i$, the $i$-th stack has the same number of haybales in both sequences.

Input Format

The first line of input contains $T$, the number of independent subtasks. You must answer all of them correctly to pass the entire test.

Each subtask contains $N$ and a sequence of $N$ heights. The input guarantees that the sum of $N$ over all subtasks does not exceed $5000$.

Output Format

Output $T$ lines. Each line should contain the answer for one subtask.

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

Hint

[Sample Explanation]

For the first subtask, the four possible height sequences are:

$(2,2,2,3),(2,2,3,2),(2,3,2,2),(3,2,2,2)$.

For the second subtask, the four possible height sequences are:

$(2,3,3,1),(3,2,3,1),(3,3,2,1),(3,3,1,2)$.

[Constraints]

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

Problem by: Daniel Zhang.

Translated by ChatGPT 5