P8100 [USACO22JAN] Counting Haybales P

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.

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 $T$ lines. Each line should contain the answer for one subtask.

[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