Usually in competitive programming you're given a problem in which you need to design an efficient algorithm that solves that problem and implement it, but for this problem we decided to take it easy on you and just give you the algorithm, so that your only task is to implement it.
The algorithm goes like this:
You are given the elements $a_i$, print the value of $f (1, n)$ modulo $10^9 + 7$.
The first line of input contains a single integer $T$ ($1 <= T <= 16$), the number of test cases.
The first line of each test case contains a single integer $n$ ($1 <= n <= 10^6$), the number of elements of array $a$.
The second line contains $n$ space-separated integers $a_1, a_2,..., a_n$ ($1 <= a_i <= 10^9$).
The sum of $n$ over all test cases doesn't exceed $4 times 10^6$.
For each test case, output a single line with the value of the function $f (1, n)$ modulo $10^9 + 7$.
## Input
The first line of input contains a single integer $T$ ($1 <= T <= 16$), the number of test cases.The first line of each test case contains a single integer $n$ ($1 <= n <= 10^6$), the number of elements of array $a$.The second line contains $n$ space-separated integers $a_1, a_2,..., a_n$ ($1 <= a_i <= 10^9$).The sum of $n$ over all test cases doesn't exceed $4 times 10^6$.
## Output
For each test case, output a single line with the value of the function $f (1, n)$ modulo $10^9 + 7$.
[samples]