Fence Job#10885
Fred the Farmer wants to redesign the fence around his house. The fence consists of vertical wooden planks of distinct heights. The height of the -th plank is h_i~(1 \le h_i \le n).
To redesign the fence, Fred may repeatedly perform the following operation any number of times (possibly times):
Choose a contiguous segment of planks [l, r] and level it by cutting the planks so that all of them have the same height, equal to the minimum height within that segment.
Formally, after applying the operation to the segment [l, r], the heights of the planks in this segment become
How many different fence designs can Fred obtain by applying this operation several times? Since the answer may be large, print it modulo 10^9 + 7.
Two fence designs and are considered different if there exists at least one plank whose height differs between and .
The first line contains an integer n~(1 \le n \le 3000), the number of planks in the fence.
The second line contains distinct integers h_i~(1 \le h_i \le n, 1 \le i \le n), representing the initial heights of the planks.
Print the number of different fence designs that can be obtained, modulo 10^9 + 7.
Example 1
Example 2
Example 3