Not Very Powerful

Input

The first line contains a single integer $t$ ( $1 \leq t \leq 1 0^{5}$ 1 \le t \le 10^5) $-$ the number of test cases.

The first line of each test case contains a single integer $n$ ( $1 \leq n \leq 5 \cdot 1 0^{5}$ 1 \le n \le 5 \cdot 10^5) $-$ the size of the array.

The second line of each test case contains $n$ integers $a_{i}$ a_i ( $0 \leq a_{i} \leq 1 0^{9}$ 0 \le a_i \le 10^9) $-$ the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 1 0^{5}$ 5 \cdot 10^5.

Output

For each test case, print a single integer — $f (a)$ .

Examples

Example 1

Loading

Note

In the first test case, the subsequences are $[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]$ [],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3].

$v ([]) = 0$ v([]) = 0.

$v ([1]) = (- 1)^{1} = - 1$ v([1]) = (-1)^1 = -1 , $v ([2]) = (- 2)^{1} = - 2$ v([2]) = (-2)^1 = -2 , $v ([3]) = (- 3)^{1} = - 3$ v([3]) = (-3)^1 = -3.

$v ([1, 2]) = (- 1)^{1} + (- 2)^{2} = - 1 + 4 = 3$ v([1,2]) = (-1)^1 + (-2)^2 = -1+4 = 3.

$v ([1, 3]) = (- 1)^{1} + (- 3)^{2} = - 1 + 9 = 8$ v([1,3]) = (-1)^1 + (-3)^2 = -1+9 = 8.

$v ([2, 3]) = (- 2)^{1} + (- 3)^{2} = - 2 + 9 = 7$ v([2,3]) = (-2)^1 + (-3)^2 = -2+9 = 7.

$v ([1, 2, 3]) = (- 1)^{1} + (- 2)^{2} + (- 3)^{3} = - 1 + 4 - 27 = - 24$ v([1,2,3]) = (-1)^1 + (-2)^2 + (-3)^3 = -1 + 4 - 27 = -24.

So $f (a) = 0 - 1 - 2 - 3 + 3 + 8 + 7 - 24 = - 12$ f(a) = 0-1-2-3+3+8+7-24 = -12.

$- 12$ mod $1000000007$ = $999999995$ .

Scoring

Subtask $1$ ( $300$ points): No additional constraints.