876. Sum of Total Strength of Wizards

0

Hard

As the ruler of a kingdom, you have a group of wizards under your command.
You are given an array called 'strength' which represents the strength of each wizard. The strength of a group of wizards is determined by multiplying the strength of the weakest wizard in the group by the sum of the strengths of all the wizards in the group.
Your task is to calculate the sum of the total strengths of all possible contiguous groups of wizards. Since the answer may be very large, return it modulo 10^9 + 7.
A subarray is 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

Loading...

View Submissions

Console