21910번 - Fence Job 다국어

문제

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$.

제한

힌트