Fred the Farmer wants to redesign the fence of his house. Fred's fence is composed of vertical wooden planks of various heights. The -th plank's height is h_i (1 \leq h_i \leq n). Initially, all heights are distinct.
In order to redesign the fence, Fred will choose some contiguous segment 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}, ..., h_r \} for all l \leq i \leq 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 and are different if there is some plank that has a different height in than in .
The first line of the input contains (1 \leq n \leq 3\,000), the number of planks of Fred's fence.
The second line contains distinct integers h_i (1 \leq h_i \leq n, 1 \leq i \leq 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.
Example 1
Example 2
Example 3