Dado un arreglo de \(n\) enteros positivos, suma el mínimo de cada uno de sus \(n(n+1)/2\) subarreglos contiguos. Como el resultado puede ser enorme, imprímelo módulo \(10^9 + 7\).

Entrada

La primera línea tiene \(n\) \((1 \le n \le 10^5)\). La segunda tiene los \(n\) enteros, entre \(1\) y \(3 \cdot 10^4\).

Salida

La suma, módulo \(10^9 + 7\).

Ejemplo 1

Entrada

4
3 1 2 4

Salida

17

Ejemplo 2

Entrada

5
11 81 94 43 3

Salida

444