310347: CF1817E. Half-sum

E. Half-sumtime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You're given a multiset of non-negative integers $\{a_1, a_2, \dots, a_n\}$.

In one step you take two elements $x$ and $y$ of the multiset, remove them and insert their mean value $\frac{x + y}{2}$ back into the multiset.

You repeat the step described above until you are left with only two numbers $A$ and $B$. What is the maximum possible value of their absolute difference $|A-B|$?

Since the answer is not an integer number, output it modulo $10^9+7$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 10^6$) — the size of the multiset.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — the elements of the multiset.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

Output

For each test case, output a single integer, the answer to the problem modulo $10^9+7$.

Formally, let $M = 10^9+7$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output an integer $x$ such that $0 \le x < M$ and $x \cdot q \equiv p \pmod{M}$.

ExampleInput

5
2
7 3
4
1 2 10 11
3
1 2 3
6
64 32 64 16 64 0
4
1 1 1 1

Output

4
9
500000005
59
0

Note

In the first case, you can't do any operations, so the answer is $|7-3|=4$.

In the second case, one of the optimal sequence of operations:

1. Substitute $1$ and $2$ with $1.5$;
2. Substitute $10$ and $11$ with $10.5$;
3. The difference between $1.5$ and $10.5$ is $9$.

In the third case, the exact answer is $\frac{3}{2}$, and $500\,000\,005 \cdot 2 \equiv 3 \pmod{10^9+7}$.

题目大意：
给定一个非负整数多重集合{a1, a2, …, an}。每一步操作从集合中取出两个元素x和y，将它们从集合中删除，并将它们的平均值(x+y)/2插入回集合中。重复上述步骤，直到只剩下两个数字A和B。求A和B的绝对差值|A-B|的最大可能值。由于答案不是整数，将结果模10^9+7输出。

输入输出数据格式：
输入：
第一行包含一个整数t(1≤t≤100)，表示测试用例的数量。
接下来每个测试用例的描述如下：
第一行包含一个整数n(2≤n≤10^6)，表示多重集合的大小。
第二行包含n个整数a1, a2, …, an(0≤ai≤10^9)，表示多重集合的元素。
所有测试用例的n之和不超过10^6。

输出：
对于每个测试用例，输出一个整数，表示问题的答案模10^9+7。题目大意： 给定一个非负整数多重集合{a1, a2, …, an}。每一步操作从集合中取出两个元素x和y，将它们从集合中删除，并将它们的平均值(x+y)/2插入回集合中。重复上述步骤，直到只剩下两个数字A和B。求A和B的绝对差值|A-B|的最大可能值。由于答案不是整数，将结果模10^9+7输出。 输入输出数据格式： 输入： 第一行包含一个整数t(1≤t≤100)，表示测试用例的数量。 接下来每个测试用例的描述如下： 第一行包含一个整数n(2≤n≤10^6)，表示多重集合的大小。 第二行包含n个整数a1, a2, …, an(0≤ai≤10^9)，表示多重集合的元素。 所有测试用例的n之和不超过10^6。 输出： 对于每个测试用例，输出一个整数，表示问题的答案模10^9+7。