#PU1189. USACO 2022 January Contest, Platinum — Problem 2. Counting Haybales

    ID: 1495 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:jan22来源:usaco.orgscoring:equal_test_cases栈排序组合数学

USACO 2022 January Contest, Platinum — Problem 2. Counting Haybales

USACO 2022 January Contest, Platinum — Problem 2. Counting Haybales

题目描述

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

输入格式

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

输出格式

Please output TT lines, one for each test case.

数据范围

Inputs 1-3 satisfy N≤10N\le 10.

样例

样例 1

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
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).$$