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