Sum of Subarray Minimums

Given an array $A$ of integers. Find the sum of $min(a_i,a_{i+1},...,a_j)$ for every pair $(i,j)$, where $1\le i\le j\le n$.

Input

The first line contains the size $n(1\le n\le 10^5)$ of array $A$. The second line contains $n$ integers $a_i(1\le a_i\le 10^5)$ — the elements of array.

Output

Print the the sum of $min(a_i,a_{i+1},...,a_j)$ modulo $10^9+7$.

Examples

Consider the first test case.

Subarrays are $\{3\},\{1\},\{2\},\{4\},\{3,1\},\{1,2\},\{2,4\},\{3,1,2\},\{1,2,4\},\{3,1,2,4\}$.

Minimums are $3,1,2,4,1,1,2,1,1,1$. Their sum is $17$.