문제
여느 때와 같이 배씨가 농부 존의 헛간에서 말썽을 일으키고 있습니다. 존에게는 N(1≤N≤5000) 건초 더미가 있습니다.
각 i∈[1,N]에 대해 i번째 스택에는 hi(1≤hi≤109) 건초 더미가 있습니다.
배씨는 건초 더미가 떨어지는 것을 원하지 않으므로 그녀가 수행할 수 있는 유일한 작업은 다음과 같습니다.
인접한 두 더미의 높이가 정확히 1 차이가 나는 경우 더 높은 더미의 맨 위 건초더미를 더 짧은 더미로 이동할 수 있습니다.
위의 작업을 모듈로 109+7로 유한하게 여러 번 수행한 후 얻을 수 있는 구성은 몇 개입니까?
모든 i에 대해 i번째 건초 더미가 모두 동일한 수의 건초 더미를 갖는 경우 두 구성은 동일한 것으로 간주됩니다.
입력
첫 번째 줄에는 테스트 케이스의 수인 T(1≤T≤10)가 주어진다.
각 테스트 케이스는 N과 N개의 높이 수열이 주어진다.
모든 테스트 케이스에 대한 N의 합이 5000을 초과하지 않도록 보장한다.
출력
각 테스트 케이스에 대해 한 줄 씩 답을 출력하시오.
예제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
힌트
출처
USACO 2022 January Platinum