483. Sum of Total Strength of Wizards

0

Hard

As the ruler of a kingdom, you have a powerful army of wizards under your command. You are provided with an array called 'strength', where each element 'strength[i]' represents the strength of the 'i-th' wizard. The total strength of a contiguous group of wizards is calculated as the product of two values: 1. The strength of the weakest wizard in the group. 2. The sum of the individual strengths of all the wizards in the group. Your task is to calculate the sum of the total strengths of all the contiguous groups of wizards. Since the answer may be very large, return it modulo 10^9 + 7. A subarray is defined as a contiguous non-empty sequence of elements within an array.

Input Format

The first line contains an integer 'N', which represents the size of the array. The next line consists of 'N' space-separated integers, representing the elements of the array.

Output Format

An integer representing the total strengths of the wizards.

Example

Input

3 5 4 6

Output

213

Constraints

1 <= N <= 10^4