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$. \InputFile 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. \OutputFile 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$.