체육 수업

체육 수업 시간에 포마는 흥미로운 활동을 생각해 냈다.

학생들이 한 줄로 선 뒤, 포마는 학생마다 고유 번호를 하나씩 주었다. 이제 그는 학생들에게 다음 조건을 모두 만족하도록 그룹으로 나뉘어 달라고 요청한다.

• 각 그룹은 줄의 연속된 구간이다. 즉 그룹에 속한 학생들은 줄에서 바로 이어서 서 있다.
• 그룹끼리 서로 겹치지 않는다.
• 각 그룹에서 학생들의 번호 수열은 단조 비감소이거나 단조 비증가이다.

여러 방법을 따져 보던 포마는 이렇게 나누는 방법이 모두 몇 가지인지 궁금해졌다. 포마는 학생들을 이런 그룹으로 나누는 방법의 수를 계산하는 프로그램을 작성해 달라고 부탁한다.

첫 번째 줄에 학생 수 $n$ ($1 \le n \le 5000$)이 주어진다. 두 번째 줄에는 학생들의 고유 번호 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$)이 순서대로 주어진다.

나눔 방법의 수를 한 줄에 출력한다. 답이 매우 클 수 있으므로 $10^9+7$로 나눈 나머지를 출력한다.