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 hi (1 ≤ hi ≤ 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 hi' = min{hl, hl+1, ..., hr} 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 109 + 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 hi (1 ≤ hi ≤ 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, modulo 109 + 7.