Suppose that you are given a histogram with heights $h_1, h_2, \cdots, h_N$. Formally, a histogram is defined as the following collection of points: $$ \bigcup_{i=1}^N \{ (x, y) : i-1 \le x < i,\, 0 \le y < h_i \}. $$

You may choose $N$ integers $x_1, x_2, \cdots, x_N$ with $1 \le x_i < h_i$ and subtract a sub-histogram with heights $x_1, x_2, \cdots, x_N$. After removing such sub-histogram, the remaining area can be written as: $$ \bigcup_{i=1}^N \{ (x, y) : i-1 \le x < i,\, x_i \le y < h_i \}. $$

The following figure shows an example with $h_1 = 4$, $h_2 = 5$, $h_3 = 4$, $h_4 = 4$ and $x_1 = 1$, $x_2 = 2$, $x_3 = 3$, $x_4 = 2$.

The remaining area is connected if for every pair of points $(p, q)$ in the remaining area, there's a curve from $p$ to $q$ that stays strictly inside the remaining area.

Compute the number of ways choosing $(x_1, x_2, \cdots, x_N)$ that the remaining area is connected.

Input

On the first line, an integer $N$ is given. On the second line, $N$ integers $h_1, h_2, \cdots, h_N$ are given.

Constraints

• $1 \le N \le 250,000$
• $2 \le h_i < 10^9$

Subtasks

Subtask 1

$N \le 3$, $h_i \le 100$ for $i = 1, 2, \cdots, N$

Subtask 2

$N \le 3$

Subtask 3

$h_1 = h_2 = \cdots = h_N$

Subtask 4

$h_1 \le h_2 \le \cdots \le h_N$

Subtask 5

No additional constraints.

Output

Output the number of possible ways to choose $(x_1, x_2, \cdots, x_N)$ such that the remaining area is connected modulo $10^9 + 7$.