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$