Eraser

Seunghyun is worried that someone will ruin his erasers, so he decided to make his own.

Seunghyun picks a sequence of natural numbers $a_1, a_2, \dots, a_n$. He then chooses three elements $a_i$, $a_j$, $a_k$ at three different positions of the sequence and builds a rectangular eraser whose width, depth and height are those three values. He calls it the $i-j-k$ eraser. Seunghyun likes erasers that are tall and thin, so $a_i < a_j < a_k$ must hold.

Look at the picture above. Let the sequence be $a_1 = 3$, $a_2 = 1$, $a_3 = 1$, $a_4 = 2$. The $1-2-3$ eraser cannot be made, because $3 < 1 < 1$ is false. The $2-4-1$ eraser can be made, because $1 < 2 < 3$ is true. The only erasers that can be made from this sequence are the $2-4-1$ eraser and the $3-4-1$ eraser.

Seunghyun wants to know the total volume of every eraser he can make. The volume of an eraser is the product of its width, depth and height. He needs that number to design the warehouse where the erasers will be stacked, so help him compute it.

The first line contains the length $n$ of the sequence. ($1 \le n \le 100{,}000$)

The second line contains $a_1, a_2, \dots, a_n$ in order, separated by spaces. ($1 \le a_i \le 100{,}000$)

Print the sum of the volumes of every eraser that can be made. Seunghyun wants to check that the program runs correctly first, so print that sum modulo $1{,}000{,}000{,}007$ ($10^9 + 7$).

Take the sequence $a_1 = 3$, $a_2 = 1$, $a_3 = 1$, $a_4 = 2$. The only erasers that can be made are the $2-4-1$ eraser and the $3-4-1$ eraser, so the total volume is $a_2 a_4 a_1 + a_3 a_4 a_1 = 1 \times 2 \times 3 + 1 \times 2 \times 3 = 12$.