E. Полусумма
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано мультимножество неотрицательных целых чисел $$$\{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}$$$. Выведите целое число, равное $$$p \cdot q^{-1} \bmod M$$$. Другими словами, выведите такое целое число $$$x$$$, что $$$0 \le x < M$$$ и $$$x \cdot q \equiv p \pmod{M}$$$.

Пример
Входные данные
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
Выходные данные
4
9
500000005
59
0
Примечание

В первом примере вы не можете выполнить никаких операций, поэтому ответ равен $$$|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}$$$.