У Фермера Джона є \(N\) (\(1\leq N \leq 5000\)) стогів з тюків сіна. Для кожного \(i\in [1,N]\), \(i\)-ий стог має висоту \(h_i\) (\(1\le h_i\le 10^9\)) тюків.

Бесі може виконувати таку операцію:

• Якщо висоти сусідніх стогів сіна відрізняються рівно на 1, вона може перемістити верхній тюк сіна з вищого стогу на менш високий.

Скільки конфігурацій за модулем \(10^9+7\) можна отримати після виконання цієї операції кінцеве число разів? Дві конфігурації розглядаються як та сама якщо для всіх \(i\) кожен стог сіна містить одне й теж кількість тюків в обох стогах.

Формат вхідних даних

Перший рядок введення містить \(T\) (\(1\le T\le 10\)), кількість незалежних тестів кожен із яких має бути вирішений правильно.

Кожен тест складається з \(N\), і послідовності \(N\) висот. Гарантується, що сума всіх \(N\) у всіх \(T\) тестах не перевищить \(5000\).

Формат вихідних даних

Виведіть \(T\) рядків по одному для кожного тесту.

Приклад вхідних даних

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

Для першого тесту чотири можливі конфігурації такі:

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

ОЦІНЮВАННЯ:

• У тестах 1-3 N≤10.
• У тесті 4 1≤hi≤3 для всіх i.
• У тестах 5-7 |hi−i|≤1 всім i.
• У тестах 8-10 1≤hi≤4 для всіх i та N≤100.
• У тестах 11-13 N≤100.
• В тестах 14-17 N≤1000.
• В тестах 18-21 немає додаткових обмежень.

Автор: Daniel Zhang