| Codeforces Round 415 (Div. 1) |
|---|
| Закончено |
Устав от жизни в Банкополисе, Леха решил переехать в тихий городок Вичкополис. По приезду он сразу же начал расширять сеть взломанных им компьютеров. За неделю Леха успел получить доступ к n компьютерам по всему городу. А так как в Вичкополисе только одна прямая улица, то и все компьютеры, взломанные Лехой, находятся на одной прямой.
Введем систему координат на единственной улице Вичкополиса. Пронумеруем все компьютеры, взломанные хакером, целыми числами от 1 до n. Тогда i-й компьютер, взломанный Лехой, находится в точке с координатой xi. При этом местоположения всех компьютеров попарно различны.
После трудной недели Лехе потребовался отдых. Поэтому он решил пригласить свою знакомую Нуру в ресторан. Однако девушка согласилась идти на свидание только с одним условием: Леха должен решить поставленную ей задачу.
Нура хочет, чтобы Леха посчитал сумму F(a) для всех a, где a — непустое подмножество множества взломанных Лехой компьютеров. Более формально, обозначим множество целых чисел от 1 до n включительно как A. Нура просит хакера найти значение 
. При этом F(a) вычисляется как максимум среди расстояний между всеми парами компьютеров, вошедших во множество a. Более формально, 
. Так как ответ может получиться достаточно большим, Нура просит найти значение интересующей ее суммы по модулю 109 + 7.
Однако Леха так устал, взламывая компьютеры, что уже не может решить эту задачку. Помогите хакеру попасть на свидание с Нурой.
В первой строке задано одно целое число n (1 ≤ n ≤ 3·105) — количество компьютеров, взломанных Лехой.
Во сторой строке задано n целых чисел x1, x2, ..., xn (1 ≤ xi ≤ 109) — координаты взломанных хакером компьютеров. Гарантируется, что все числа xi попарно различны.
Выведите одно число — значение суммы, которую просит найти Нура, по модулю 109 + 7.
2
4 7
3
3
4 3 1
9
Рассмотрим первый тест. У нас есть всего три подмножества 
, 
и 
. В первых двух к итоговой сумме прибавится 0, а в третьем 7 - 4 = 3. Итого ответ 0 + 0 + 3 = 3.
Во втором тесте у нас есть семь подмножеств, из них ответ увеличат следующие: 
, 
, 
, 
. Итого ответ (4 - 3) + (4 - 1) + (3 - 1) + (4 - 1) = 9.
