У Фермера Джона есть \(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\) строк по одной для каждого теста.
Ваш ответ: