건초 더미 세기

Bessie 소가 Farmer John의 헛간에서 또 말썽을 일으키고 있다. FJ에게는 $N$개($1 \le N \le 5000$)의 건초 더미가 있다. 각 $i \in [1, N]$에 대해 $i$번째 더미에는 $h_i$개($1 \le h_i \le 10^9$)의 건초 베일이 쌓여 있다. Bessie는 건초가 떨어지는 것을 원하지 않으므로, 그녀가 할 수 있는 연산은 다음 하나뿐이다.

• 인접한 두 더미의 높이 차이가 정확히 1이면, 높은 더미의 맨 위 건초 베일 하나를 낮은 더미로 옮길 수 있다.

이 연산을 유한번 수행하여 얻을 수 있는 배치의 개수를 구하라. 답은 $10^9+7$로 나눈 나머지로 출력한다. 모든 $i$에 대해 $i$번째 더미의 건초 개수가 같으면 두 배치는 같은 배치로 본다.

첫 줄에 독립적인 테스트 케이스의 개수 $T$($1 \le T \le 10$)가 주어진다. 모든 테스트 케이스를 맞혀야 입력 하나를 맞힌 것으로 본다.

각 테스트 케이스는 $N$과 이어서 $N$개의 높이로 이루어진다. 모든 테스트 케이스의 $N$ 합은 $5000$을 넘지 않는다.

$T$줄을 출력한다. 각 줄은 테스트 케이스 하나의 답이다.

첫 번째 테스트 케이스에서 가능한 배치는 네 가지이다.

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

두 번째 테스트 케이스에서 가능한 배치도 네 가지이다.

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