# SEERC 2021

# 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`

' = min{_{i}`h`

, _{l}`h`

, ..., _{l+1}`h`

} for all _{r}**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, modulo
`10`

+ ^{9}**7**.

3 1 3 2

4

5 1 2 3 4 5

42

7 1 4 2 5 3 6 7

124