Работа с забором
Фермер Фред хочет переделать забор в своем доме. Забор Фреда состоит n вертикальных деревянных досок разной высоты. Высота i-ой доски равна h[i] (1 ≤ h[i] ≤ n). Изначально все высоты различны.
Чтобы изменить конструкцию забора, Фред выбирает несколько смежных сегментов [l ... r] досок и “выравнивает“ их, разрезав так, чтобы все высоты были равны минимальной высоте на этом сегменте. Более конкретно, новые высоты сегмента становятся h[i]' = min{h[l], h[l+1], ..., h[r]} для всех l ≤ i ≤ r.
Сколько различных конструкций может получить Фред, применив эту процедуру несколько (возможно, 0) раз? Поскольку ответ может быть большим, выведите его по модулю 10^9 + 7.
Две конструкции A и B отличаются, если есть доска, высота которой в A отличается от высоты в B.
Входные данные
Первая строка содержит количество досок n (1 ≤ n ≤ 3000) забора Фреда.
Вторая строка содержит n различных целых чисел h[i] (1 ≤ h[i] ≤ n, 1 ≤ i ≤ n) - высоты каждой из досок.
Выходные данные
Выведите одно целое число - количество различных возможных конструкций забора, которое можно получить, по модулю 10^9 + 7.