Remove the element
/

## Algorithms, Easy-Medium, Greedy algorithm

Problem
Editorial
Analytics

You are given an integer array A of size N. You can perform an operation exactly N number of times. In the operation, you can remove one element from the array A and the operation will cost $A_i$ units if $i^{th}$ is removed from the array. The operation will take 1 second.

Elements of array A will keep on increasing every second until it is removed. Let $i^{th}$ element is $A_i$ at $j^{th}$ second. Then the $i^{th}$ element will increase by $(j + 1) * A_i$ and the element will become $A_i + (j+1) * A_i$ at $(j+1)^{th}$ second.

Your task is to find the minimum cost to remove all the elements from the array A. As the answer can be very large, print the answer module $10^9 + 7$.

Input Format
The first line of input contains a single integer T denoting the number of test cases.
The first line of each test case contains a single integer N denoting the number of elements in the array A.
The second line of each test case contains N space-separated integers, $i^{th}$ integer denotes $A_i$.

Output Format
Print the answer corresponding to each test case in new line.

Constraints

• $1 \le T \le 10$
• $1 \le N \le 10^5$
• $1 \le A_i \le 10^9$
SAMPLE INPUT
1
2
3 3
SAMPLE OUTPUT
9
Explanation

Initially, $j = 0$
The cost of removing the first element is 3 and it will take 1 second.
After 1 second, the second element will become $(j+1) * A_2 + A_2 = 1 * 3 + 3 = 6$ and j will become 1.
The cost of removing second element will be 6.
Total cost = $3 + 6 = 9$

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...