Устав от жизни в Банкополисе, Леха решил переехать в тихий городок Вичкополис. По приезду он сразу же начал расширять сеть взломанных им компьютеров. За неделю Леха успел получить доступ к n компьютерам по всему городу. А так как в Вичкополисе только одна прямая улица, то и все компьютеры, взломанные Лехой, находятся на одной прямой.
Введем систему координат на единственной улице Вичкополиса. Пронумеруем все компьютеры, взломанные хакером, целыми числами от 1 до n. Тогда i-й компьютер, взломанный Лехой, находится в точке с координатой xi. При этом местоположения всех компьютеров попарно различны.
После трудной недели Лехе потребовался отдых. Поэтому он решил пригласить свою знакомую Нуру в ресторан. Однако девушка согласилась идти на свидание только с одним условием: Леха должен решить поставленную ей задачу.
Нура хочет, чтобы Леха посчитал сумму F(a) для всех a, где a — непустое подмножество множества взломанных Лехой компьютеров. Более формально, обозначим множество целых чисел от 1 до n включительно как A. Нура просит хакера найти значение 
. При этом F(a) вычисляется как максимум среди расстояний между всеми парами компьютеров, вошедших во множество a. Более формально, 
. Так как ответ может получиться достаточно большим, Нура просит найти значение интересующей ее суммы по модулю 109 + 7.
Однако Леха так устал, взламывая компьютеры, что уже не может решить эту задачку. Помогите хакеру попасть на свидание с Нурой.