Let's call a subsequence of array a a non-empty array b such that it can be obtained from array a by deleting some (possibly none) elements of array a. For example, array [1,3] is a sequence of array [1,2,3] , but [3,1] is not.
Let's call a subsegment of array a a non-empty array b such that it can be obtained by deleting several (possibly none) of the first and last elements of array a. For example, [1,2] is a subsegment of the array [1,2,3] , but [1,3] is not. It is easy to see that an array of length n has exactly
\( {n(n+1) \over 2}\) subsegments.
Let's call an array a of length n increasing if for any 1 ≤ i≤ n a
i ≤ a
i+1.
The monotonicity of an array is the number of its increasing subsegments.
Given an array a of length n. Calculate the sum of monotonicities over all its subsequences. Since the answer can be very large, print it modulo 10
9+7.
Input
The first line contains an integer n (1 ≤ n ≤ 200000) — array length a.
The second line contains n integers (1 ≤ a
i ≤ 200000) — array elements a.
Imprint
Print a single integer — the sum of the monotonicities of all subsequences modulo 10
9+7.
Note
In the first test case, the array has 7 subsequences:
- Array [1] has exactly one subsegment and is ascending.
- The array [2] has exactly one subsegment and is increasing.
- The array [3] has exactly one subsegment and is increasing.
- The array [1,2] has three subsegments ([1], [2], [1,2] ) and they are all increasing.
- The array [1,3] has three subsegments ([1], [3], [1,3] ) and they are all increasing.
- The array [3,2] has three subsegments ([3], [2], [3, 2] ), but only two of them ([3] and [2] ) are ascending.
- The array [1,3,2] has six subsegments ([1], [3], [2], [1,3], [3,2], [1,3,2] ) and four of them ([1], [3], [2], [1,3] ) are increasing.
In the second test case, all increasing subsegments of all subsequences have length 1.
Examples
| # |
Input |
Output |
| 1 |
3
1 3 2
| 15 |
| 2 |
3
6 6 6
| 12 |