Робота з парканом
Фермер Фред планує оновити паркан у своєму господарстві. Паркан складається з n вертикальних дерев'яних дощок, кожна з яких має різну висоту. Висота i-ї дошки позначена як h[i] (1 ≤ h[i] ≤ n), і всі ці висоти є унікальними.
Фред може змінювати конструкцію паркану, вибираючи кілька суміжних дощок у сегменті [l ... r] і "вирівнюючи" їх, тобто обрізаючи так, щоб усі дошки в цьому сегменті мали однакову висоту, яка дорівнює мінімальній висоті в обраному сегменті. Точніше, нова висота кожної дошки в сегменті стає h[i]' = min{h[l], h[l+1], ..., h[r]} для всіх l ≤ i ≤ r.
Завдання полягає в тому, щоб визначити, скільки різних конструкцій паркану може отримати Фред, застосовуючи цю процедуру кілька разів (можливо, жодного разу). Оскільки кількість можливих конструкцій може бути великою, результат потрібно вивести за модулем 10^9 + 7.
Вхідні дані
Перший рядок містить число n (1 ≤ n ≤ 3000), яке вказує на кількість дощок у паркані Фреда.
Другий рядок містить n різних цілих чисел h[i] (1 ≤ h[i] ≤ n, 1 ≤ i ≤ n), що представляють висоти кожної з дощок.
Вихідні дані
Виведіть одне ціле число — кількість різних можливих конструкцій паркану, яке можна отримати, за модулем 10^9 + 7.