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 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 h0 i = 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 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 of the input 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 10^9 + 7.

Examples

Input

3
1 3 2

Output

4

Input

5
1 2 3 4 5

Output

42

Input

7
1 4 2 5 3 6 7

Output

124