A. Хочешь на свидание?
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Устав от жизни в Банкополисе, Леха решил переехать в тихий городок Вичкополис. По приезду он сразу же начал расширять сеть взломанных им компьютеров. За неделю Леха успел получить доступ к 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.