시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB39272270.968%

문제

Fred the Farmer wants to redesign the fence of his house. Fred’s fence is composed of $n$ vertical wooden planks of various heights. The $i$-th plank’s height is $h_i$ ($1 \le h_i \le n$). Initially, all heights are distinct.

In order to redesign the fence, Fred will choose some contiguous segment $[l\dots r]$ of planks and “level” them, by cutting them in order to make all heights equal to the minimum height on that segment. More specifically, the new heights of the segment become $h'_i = \min{\{h_l, h_{l+1}, \dots, h_r\}}$ for all $l \le i \le r$.

How many different designs can Fred obtain by applying this procedure several (possibly $0$) times? Since the answer may be huge, you are required to output it modulo $10^9 + 7$.

Two designs $A$ and $B$ are different if there is some plank that has a different height in $A$ than in $B$.

입력

The first line of the input contains $n$ ($1 \le n \le 3\,000$), the number of planks of Fred’s fence.

The second line contains $n$ distinct integers $h_i$ ($1 \le h_i \le n$, $1 \le i \le n$), the heights of each of the planks.

출력

Output a single integer, the number of different possible fence designs that can be obtained, modulo $10^9 + 7$.

예제 입력 1

3
1 3 2

예제 출력 1

4

예제 입력 2

5
1 2 3 4 5

예제 출력 2

42

예제 입력 3

7
1 4 2 5 3 6 7

예제 출력 3

124