Codeforces and Polygon may be unavailable from May 23, 4:00 (UTC) to May 23, 8:00 (UTC) due to technical maintenance. ×

F. Fence Job
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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 \leq h_i \leq 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 $$$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 $$$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 \leq n \leq 3\,000$$$), the number of planks of Fred's fence.

The second line contains $$$n$$$ 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
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