Đếm Kiện Cỏ Khô

Cho $N$ cọc có chiều cao $h_1,h_2,\dots ,h_N$. Bạn có thể thực hiện một loại thao tác: nếu hai cọc liền kề có chiều cao chênh nhau đúng $1$, hãy chuyển một đơn vị từ cọc cao hơn sang cọc thấp hơn (tức là giảm chiều cao cọc cao đi $1$ và tăng chiều cao cọc thấp lên $1$).

Hãy đếm số cấu hình $(h_1^{\prime },h_2^{\prime },\dots ,h_N^{\prime })$ phân biệt có thể đạt được sau khi thực hiện các thao tác trên một số lần tùy ý (có thể không thực hiện), kể cả cấu hình ban đầu. Kết quả lấy modulo ${10}^9+7$.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $T$ — số lượng test case.

Mỗi test case gồm hai dòng:

• Dòng đầu: số nguyên $N$.
• Dòng thứ hai: $N$ số nguyên $h_1,h_2,\dots ,h_N$.

Dữ liệu ra

In ra $T$ dòng, mỗi dòng chứa số cấu hình có thể đạt được của test case tương ứng, modulo ${10}^9+7$.

Ràng buộc

• $1\le T\le 10$
• $1\le N\le 5000$
• $1\le h_i\le {10}^9$
• Tổng $N$ qua tất cả các test case không vượt quá $5000$

Ví dụ

Ghi chú

Thao tác cho phép tương đương với hoán đổi hai phần tử liền kề có giá trị chênh nhau đúng $1$. Từ đó, bài toán quy về đếm số thứ tự topo của một đồ thị có hướng: tồn tại cạnh $i\to j$ (với $i<j$) khi $|h_i-h_j|\ne 1$ (tức là không thể hoán đổi).