QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100
[0]

# 2472. Counting Haybales

Statistics

As usual, Bessie the cow is causing trouble in Farmer John's barn. FJ has N (1N5000) stacks of haybales. For each i[1,N], the ith stack has hi (1hi109) 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 109+7? Two configurations are considered the same if, for all i, the ith stack has the same number of haybales in both.

Input Format

The first line contains T (1T10), 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

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

  • Inputs 1-3 satisfy N10.
  • Input 4 satisfies 1hi3 for all i.
  • Inputs 5-7 satisfy |hii|1 for all i.
  • Inputs 8-10 satisfy 1hi4 for all i and N100.
  • Inputs 11-13 satisfy N100.
  • Inputs 14-17 satisfy N1000.
  • Inputs 18-21 satisfy no additional constraints.

Problem credits: Daniel Zhang