Фермер Фред хочет переделать забор в своем доме. Забор Фреда состоит n вертикальных деревянных досок разной высоты. Высота i-ой доски равна hi (1 ≤ hi ≤ n). Изначально все высоты различны.

Чтобы изменить конструкцию забора, Фред выбирает несколько смежных сегментов [l ... r] досок и “выравнивает“ их, разрезав так, чтобы все высоты были равны минимальной высоте на этом сегменте. Более конкретно, новые высоты сегмента становятся hi' = min{hl, hl+1, ..., hr} для всех l ≤ i ≤ r.

Сколько различных конструкций может получить Фред, применив эту процедуру несколько (возможно, 0) раз? Поскольку ответ может быть большим, выведите его по модулю 109 + 7.

Две конструкции A и B отличаются, если есть доска, высота которой в A отличается от высоты в B.

Входные данные

Первая строка содержит количество досок n (1 ≤ n ≤ 3000) забора Фреда.

Вторая строка содержит n различных целых чисел hi (1 ≤ hi ≤ n, 1 ≤ i ≤ n) - высоты каждой из досок.

Выходные данные

Выведите одно целое число - количество различных возможных конструкций забора, которое можно получить, по модулю 109 + 7.