eolymp
bolt
Try our new interface for solving problems
Problems

Fence Job

Fence Job

Time limit 1 second
Memory limit 256 MiB

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] (1h[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 lir.

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 data

The first line contains n (1n3000), the number of planks of Fred’s fence.

The second line contains n distinct integers h[i] (1h[i]n, 1in), the heights of each of the planks.

Output data

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

Examples

Input example #1
3
1 3 2
Output example #1
4
Input example #2
5
1 2 3 4 5
Output example #2
42
Input example #3
7
1 4 2 5 3 6 7
Output example #3
124
Source 2020 SEERC South Eastern European Regional Programming Contest, Vinnica & Bucharest, May 23, Problem F