SOLVE

LATER

Remove the element

/

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\)

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