System Vulnerabilities

The vulnerability of each non-empty contiguous segment is its length multiplied by its maximum element. Find the sum of the vulnerabilities of all contiguous segments, modulo 1000000007.

输入格式

The first line contains n (1..100000); the second line contains n vulnerability values (1..10⁹).

输出格式

Output one integer, the answer required by the problem.

样例 1

输入：

3
3 1 4

输出：

34

样例 2

输入：

2
2 2

输出：

8

样例 3

输入：

1
1

输出：

1

样例说明

Example 1: the six contiguous segments contribute 3, 6, 12, 1, 8 and 4 in order, for a total of 34. Example 2: the two single-element segments contribute 2 each, and the whole segment contributes 2×2=4, for a total of 8. Example 3: the only segment contributes 1.