CF1817E.Half-sum

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$.

给你一个非负整数的多重集 $\{a_1, a_2, \dots, a_n\}$。

每一步中，你从该多重集中选取两个元素 $x$ 和 $y$，将它们移除，并将它们的平均值 $\frac{x + y}{2}$ 重新插入该多重集。

你重复上述操作，直到多重集中仅剩下两个数 $A$ 和 $B$。问：它们的绝对差 $|A-B|$ 的最大可能值是多少？

由于答案不一定是整数，请将结果对 $10^9+7$ 取模后输出。

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。随后是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^6$）—— 多重集的大小。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$）—— 多重集的元素。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

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 \lt M$ and $x \cdot q \equiv p \pmod{M}$.

对于每个测试用例，输出一个整数，即问题答案对 $10^9+7$ 取模的结果。

形式化地，令 $M = 10^9+7$。可以证明答案可表示为既约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 为整数，且 $q \not \equiv 0 \pmod{M}$。请输出整数 $p \cdot q^{-1} \bmod M$。换言之，输出满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

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}$.

第一种情况，你无法进行任何操作，因此答案为 $|7-3|=4$。

第二种情况，一种最优的操作序列如下：

1. 将 $1$ 和 $2$ 替换为 $1.5$；
2. 将 $10$ 和 $11$ 替换为 $10.5$；
3. $1.5$ 与 $10.5$ 的差为 $9$。

第三种情况，精确答案为 $\frac{3}{2}$，且满足 $500\,000\,005 \cdot 2 \equiv 3 \pmod{10^9+7}$。