E. Half-sum
brute force; divide and conquer; greedy
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\).
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\).
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}\).
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: Substitute \(1\) and \(2\) with \(1.5\); Substitute \(10\) and \(11\) with \(10.5\); 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}\).