#USACOC2221B. Counting Haybales

Counting Haybales

Description

As usual, Bessie the cow is causing trouble in Farmer John's barn. FJ has NN stacks of haybales. For each i[1,N]i\in [1,N], the iith stackhas hih_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 109+710^9+7? Two configurations are considered the sameif, for all ii, the iith stack has the same number of haybales in both.

  • 1N50001\leq N \leq 5000
  • 1hi1091\le h_i\le 10^9

Input Format

The first line contains TT (1T101\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 NN, and then a sequence of NN heights. It isguaranteed that the sum of NN over all test cases does not exceed 50005000.

Output Format

Please output TT 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 N10N\le 10.
  • Input 4 satisfies 1hi31\le h_i\le 3 for all ii.
  • Inputs 5-7 satisfy hii1|h_i-i|\le 1 for all ii.
  • Inputs 8-10 satisfy 1hi41\le h_i\le 4 for all ii and N100N\le 100.
  • Inputs 11-13 satisfy N100N\le 100.
  • Inputs 14-17 satisfy N1000N\le 1000.
  • Inputs 18-21 satisfy no additional constraints.

Problem Credit

Problem credits: Daniel Zhang