Урок физкультуры

На очередном уроке физкультуры Фома придумал интересное занятие.

После того как школьники выстроились в шеренгу, он дал каждому свой персональный номер. Теперь он просит школьников разбится на группы, чтобы выполнялись условия:

• Каждая группа --- это подотрезок шеренги. То есть школьники в группе стоят в шеренге подряд.
• Группы не пересекаются.
• В каждой группе последовательность персональных номеров школьников либо нестрого возрастает, либо нестрого убывает.

Перебрав несколько способов, Фома заинтересовался, сколько их может быть всего. Он просит вас написать программу, которая вычислит, сколько есть способов разбиения школьников на такие группы.

В первой строке входного файла задано число $n$ ($1 \le n \le 5000$) --- количество школьников. Во второй строке содержатся $n$ чисел $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) --- персональный номер каждого школьника.

В единственной строке выходного файла выведите одно число --- количество способов разделить школьников на группы. Ответ может быть очень большой, поэтому нужно вывести его по модулю $10^9+7$.