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 ≤ h[i] ≤ n). Initially, all heights are distinct.
In order to redesign the fence, Fred will choose some contiguous segment [l...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], ..., h[r]} for all l ≤ i ≤ 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.
Input
The first line contains n (1 ≤ n ≤ 3000), the number of planks of Fred’s fence.
The second line contains n distinct integers h[i] (1 ≤ h[i] ≤ n, 1 ≤ i ≤ n), the heights of each of the planks.
Output
Output a single integer, the number of different possible fence designs that can be obtained, modulo10^9 + 7.