\begin{problem}{Урок физкультуры}{lesson.in}{lesson.out}{2 секунды}{256 мегабайт}

%Автор задачи: Шовкопляс Григорий
%Автор условия: Шовкопляс Григорий

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

После того как школьники выстроились в шеренгу, он дал каждому свой
персональный номер. Теперь он просит школьников разбится на группы, чтобы выполнялись условия:
\begin{itemize}
    \item Каждая группа~--- это подотрезок шеренги. То есть школьники в группе стоят в шеренге подряд.
    \item Группы не пересекаются.
    \item В каждой группе последовательность персональных номеров школьников либо нестрого возрастает, либо нестрого убывает.
\end{itemize}
                         
Перебрав несколько способов, Фома заинтересовался, сколько их может быть всего. Он просит
вас написать программу, которая вычислит, сколько есть способов разбиения школьников на такие группы.
               
\InputFile
В первой строке входного файла задано число $n$ ($1 \le n \le 5000$)~--- количество школьников.
Во второй строке содержатся $n$ чисел $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$)~--- персональный номер 
каждого школьника.

\OutputFile
В единственной строке выходного файла выведите одно число~--- количество способов разделить школьников на 
группы. Ответ может быть очень большой, поэтому нужно вывести его по модулю $10^9+7$.
\Example
\begin{example}%
\exmp{
4
1 2 3 4
}{   
8
}%
\exmp{
5                                         
1 2 2 2 1
}{
15
}%
\exmp{
5                                         
1 2 1 2 1
}{
8
}%
\end{example}

\end{problem}
