Như thường lệ, cô bò Bessie đang gây rắc rối trong chuồng của Nông dân John. FJ có \(N\) (\(1\le N\le 5000\)) chồng kiện cỏ khô. Với mỗi \(i\in[1,N]\), chồng thứ \(i\) có \(h_i\) (\(1\le h_i\le 10^9\)) kiện cỏ. Bessie không muốn kiện cỏ nào bị rơi, nên thao tác duy nhất cô có thể thực hiện là:

• Nếu chiều cao của hai chồng kề nhau chênh lệch đúng một, cô có thể chuyển kiện cỏ trên cùng của chồng cao hơn sang chồng thấp hơn.

Có bao nhiêu cấu hình có thể thu được sau khi thực hiện thao tác trên hữu hạn lần, lấy modulo \(10^9+7\)? Hai cấu hình được coi là giống nhau nếu với mọi \(i\), chồng thứ \(i\) có cùng số kiện cỏ trong cả hai cấu hình.

Dữ liệu vào

Dòng đầu chứa \(T\) (\(1\le T\le 10\)), là số bộ test độc lập; cần giải đúng tất cả để giải đúng một dữ liệu vào.

Mỗi bộ test gồm \(N\), rồi một dãy \(N\) chiều cao. Đảm bảo tổng \(N\) trên mọi bộ test không vượt quá \(5000\).

Dữ liệu ra

In \(T\) dòng, mỗi dòng ứng với một bộ test.

Phân nhóm

• Các input 1–3 thỏa mãn \(N\le 10\).
• Input 4 thỏa mãn \(1\le h_i\le 3\) với mọi \(i\).
• Các input 5–7 thỏa mãn \(|h_i-i|\le 1\) với mọi \(i\).
• Các input 8–10 thỏa mãn \(1\le h_i\le 4\) với mọi \(i\) và \(N\le 100\).
• Các input 11–13 thỏa mãn \(N\le 100\).
• Các input 14–17 thỏa mãn \(N\le 1000\).
• Các input 18–21 không có ràng buộc bổ sung.

Ví dụ

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

Nguồn

USACO 2022 January Contest, Platinum — Counting Haybales: https://usaco.org/index.php?page=viewproblem2&cpid=1189

Tác giả: Daniel Zhang.