Робота з Парканом#10885
Фред Фермер хоче перепроєктувати паркан навколо свого дому. Паркан складається з вертикальних дерев'яних дощок різної висоти. Висота -тої дошки дорівнює h_i~(1 \le h_i \le n).
Щоб перепроєктувати паркан, Фред може неодноразово виконати наступну операцію будь-яку кількість разів (можливо разів):
Вибрати неперервний сегмент дощок [l, r] та вирівняти його, зрізавши дошки так, щоб всі вони мали однакову висоту, яка дорівнює мінімальній висоті у цьому сегменті.
Формально, після застосування операції до сегмента [l, r], висоти дошок у цьому сегменті стануть
Скільки різних дизайнів паркану може отримати Фред, застосовуючи цю операцію кілька разів? Оскільки відповідь може бути великою, надрукуйте її за модулем 10^9 + 7.
Два дизайни паркану та вважаються різними, якщо існує хоча б одна дошка, висота якої відрізняється між та .
Перший рядок містить ціле число n~(1 \le n \le 3000), кількість дощок у паркані.
Другий рядок містить різних цілих чисел h_i~(1 \le h_i \le n, 1 \le i \le n), що представляють початкові висоти дощок.
Надрукуйте кількість різних дизайнів паркану, які можна отримати, за модулем 10^9 + 7.
Приклад 1
Приклад 2
Приклад 3