У Фермера Джона есть \(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\)
каждый стог сена содержит одно и тоже количество тюков в обоих стогах.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка ввода содержит
\(T\) (
\(1\le T\le 10\)), количество независимых тестов
каждый из которых должен быть решён правильно.
Каждый тест состоит из \(N\), и последовательности \(N\) высот. Гарантируется,
что сумма всех \(N\) во всех \(T\) тестах не превысит \(5000\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(T\) строк по одной для каждого теста.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|