H. Expected Value Of Function
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array $$$a$$$ of length $$$n$$$ $$$(1 \le n \le 2 * 10^5)$$$ its elements are numbered from 0 to $$$n - 1$$$ $$$(a_0,a_1,...,a_{n-1})$$$.

For two integers $$$start$$$ and $$$step$$$ $$$(0 \le start,step \le n-1)$$$ define $$$f(start,step)$$$ as follows:

first set an integer $$$current$$$ to $$$start$$$ and set another integer $$$sum$$$ to zero, that is $$$current = start$$$ and $$$sum = 0$$$.Then repeat this steps $$$n$$$ times:

  1. add $$$a_{current}$$$ to $$$sum$$$, that is $$$sum = sum + a_{current}$$$.
  2. set $$$a_{current}$$$ to zero, that is $$$a_{current} = 0$$$.
  3. add $$$step$$$ to $$$current$$$ modulo $$$n$$$, that is $$$current = (current + step)$$$ $$$mod$$$ $$$n$$$
Then the value of $$$f(start,step)$$$ is $$$sum$$$.

If We Choose $$$start$$$ and $$$step$$$ randomly, what is the expected value of the function $$$f(start,step)$$$ modulo $$$10^9 + 7$$$.

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^5)$$$, the number of test cases.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \le n \le 2 * 10^5)$$$, the size of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$(1 \le a_i \le 10^9)$$$, the elements of array $$$a$$$.

It is guranteed that the sum of $$$n$$$ over all test cases doesn't exceeds $$$2 * 10^5$$$.

Output

For each test case output the expected value of the function $$$f(start,step)$$$ modulo $$$10^9 + 7$$$.

Example
Input
5
5
1 2 3 4 5
4
10 20 80 90
3
70 2 1
7
1 1 1 1 1 1 1
4
2 1 2 1000000000
Output
200000014
500000141
777777840
142857150
625000003