A. Absolute Cinema
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

After the unforgettable episode with the El Café coffee shop, Max and his brother Min decided to take a well-deserved vacation — this time, away from coffee and closer to the big screen. Their love for cinema, especially the films of Martin Scorsese, led them to create a new tradition: continuous Scorsese marathons.

During their month of rest, the brothers organized $$$N$$$ of the director's films in chronological order, numbering them from $$$1$$$ to $$$N$$$. Each film received a score from film critics; the score of the $$$i$$$-th film is $$$a_i$$$.

Being as competitive and creative as always, Max and Min decided to evaluate the quality of each "continuous marathon" in a curious way:

  • Max, unsurprisingly, cares about the maximum.
  • Min, of course, is interested in the minimum.
  • For them, the quality of a marathon is defined as the product of the maximum and the minimum values in the sequence of scores of the films watched in that marathon.

A continuous marathon is any contiguous subsequence of the original list of films — it can be a single film or all $$$N$$$ films.

Naturally, Max and Min became curious: what is the total sum of the qualities of all possible continuous marathons?

Since this value can be very large, they decided to only care about the result modulo $$$10^9 + 7$$$.

Input

The first line contains an integer $$$N$$$ $$$(1 \leq N \leq 10^5)$$$, representing the number of films in the list organized by Max and Min. The second line contains $$$N$$$ integers $$$a_1, a_2, \dots, a_N$$$ ($$$1 \leq a_i \leq 10^9$$$), representing the scores given by film critics to each film.

Output

Print a single integer, which is the remainder of the division of the total sum of the qualities of all possible continuous marathons in Max and Min's list by $$$10^9 + 7$$$.

Examples
Input
3
2 1 3
Output
22
Input
5
5 9 1 2 3
Output
230
Note

Explanation of example 1: For each contiguous subsequence (marathon), we compute the quality as the product of the maximum and minimum score values among the films in that marathon:

  • [2] → Max = 2, Min = 2, Quality = $$$2 \cdot 2 = 4$$$
  • [2,1] → Max = 2, Min = 1, Quality = $$$2 \cdot 1 = 2$$$
  • [2,1,3] → Max = 3, Min = 1, Quality = $$$3 \cdot 1 = 3$$$
  • [1] → Max = 1, Min = 1, Quality = $$$1 \cdot 1 = 1$$$
  • [1,3] → Max = 3, Min = 1, Quality = $$$3 \cdot 1 = 3$$$
  • [3] → Max = 3, Min = 3, Quality = $$$3 \cdot 3 = 9$$$

The sum of all qualities is $$$4 + 2 + 3 + 1 + 3 + 9 = 22$$$.