Counting Haybales

Bessie the cow is causing trouble in Farmer John's barn again. FJ has $N$ ($1 \le N \le 5000$) stacks of haybales. For each $i \in [1, N]$, the $i$-th stack has $h_i$ ($1 \le h_i \le 10^9$) haybales. Bessie does not want any haybales to fall, so the only operation she can perform is the following:

• If two adjacent stacks differ in height by exactly one, she can move the top haybale of the taller stack to the shorter stack.

After performing this operation any finite number of times, how many configurations can be obtained? Print the count modulo $10^9+7$. Two configurations are the same if every stack $i$ has the same number of haybales in both.

The first line contains $T$ ($1 \le T \le 10$), the number of independent test cases. All of them must be solved to get one input correct.

Each test case consists of $N$, followed by a sequence of $N$ heights. The sum of $N$ over all test cases does not exceed $5000$.

Print $T$ lines, one for each test case.

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