Вам дано мультимножество неотрицательных целых чисел \(\{a_1, a_2, \dots, a_n\}\).
Вы можете выбрать два элемента \(x\) и \(y\) из мультимножества, удалить их и вставить их полусумму \(\frac{x + y}{2}\) обратно в мультимножество.
Вы повторяете описанное выше действие до тех пор, пока не останется только два числа \(A\) и \(B\). Каково максимально возможное значение их абсолютной разности \(|A-B|\)?
Поскольку ответ не является целым числом, выведите его по модулю \(10^9+7\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — ответ на задачу по модулю \(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}\).
Примечание
В первом примере вы не можете выполнить никаких операций, поэтому ответ равен \(|7-3|=4\).
Во втором примере одна из оптимальных последовательностей операций выглядит так:
- Замените \(1\) и \(2\) на \(1.5\);
- Замените \(10\) и \(11\) на \(10.5\);
- Разница между \(1.5\) и \(10.5\) равна \(9\).
В третьем примере точный ответ равен \(\frac{3}{2}\), и \(500\,000\,005 \cdot 2 \equiv 3 \pmod{10^9+7}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|