CF1817E Half-sum

给定一个非负整数的多重集 $\{a_1, a_2, \dots, a_n\}$。 每一步，你可以选择多重集中的两个元素 $x$ 和 $y$，将它们移除，并将它们的平均值 $\frac{x + y}{2}$ 插入回多重集。 你重复上述操作，直到多重集中只剩下两个数 $A$ 和 $B$。请问这两个数的绝对值差 $|A-B|$ 的最大可能值是多少？ 由于答案不是整数，请输出其对 $10^9+7$ 取模的结果。

每个测试点包含多组测试数据。第一行包含测试用例数 $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$。

对于每组测试数据，输出一个整数，表示问题的答案对 $10^9+7$ 取模的结果。 形式化地，设 $M = 10^9+7$。可以证明答案可以表示为最简分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q \not \equiv 0 \pmod{M}$。请输出满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

在第一个样例中，你无法进行任何操作，所以答案为 $|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}$。 由 ChatGPT 4.1 翻译