countinghaybales

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

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

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

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $T$ ($1\le T\le 10$), the number of independent test cases, 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 is guaranteed that the sum of $N$ over all test cases does not exceed $5000$.

OUTPUT FORMAT (print output to the terminal / stdout):

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

SAMPLE INPUT:

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

SAMPLE OUTPUT:

4
4
5
15
9
8
19

For the first test case, the four possible configurations are:

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

For the second test case, the four possible configurations are:

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

SCORING:

  • Subtask 1 (14 Points): $N\le 10$.
  • Subtask 2 (4 Points): $1\le h_i\le 3$ for all $i$.
  • Subtask 3 (14 Points): $|h_i-i|\le 1$ for all $i$.
  • Subtask 4 (14 Points): $1\le h_i\le 4$ for all $i$ and $N\le 100$.
  • Subtask 5 (14 Points): $N\le 100$.
  • Subtask 6 (19 Points): $N\le 1000$.
  • Subtask 7 (21 Points): no additional constraints.

Problem credits: Daniel Zhang


Submitting to 'countinghaybales'


You're not logged in! Click here to login


Submitting to 'countinghaybales'


You're not logged in! Click here to login


Submitting .cpp to 'countinghaybales'


You're not logged in! Click here to login

Time Limit: 1 Seconds
Memory Limit: 1024MB
Your best score: 0
Source: USACO 2022 Jan, Platinum
Editorial: 1

Subtask Score
1 14
2 4
3 14
4 14
5 14
6 19
7 21