Fence Job#12840

Fence Job

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 .

Input

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

Output a single integer, the number of different possible fence designs that can be obtained, modulo 10^9+7.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading