问题 BW: 你想约会吗?
题目描述
Leha决定搬到一个安静的小镇维科波利斯，因为他在班科波利斯生活很累。抵达后，他立即开始扩展他的黑客计算机网络。在这一周里，Leha设法访问了整个城镇的n台计算机。顺便说一下，所有被Leha黑客入侵的计算机都位于同一条直线上，因为维科波利斯只有一条直线。
让我们表示这条街上的坐标系。此外，让我们用从 1 到 n 的整数对所有被黑客入侵的计算机进行编号。因此，第 i 台被黑客入侵的计算机位于点 xi。此外，所有计算机的坐标都是不同的。
Leha决心在辛苦的一周后休息一下。因此，他要邀请他的朋友Noora去一家餐馆。然而，女孩同意约会，唯一的条件是：Leha必须解决一个简单的任务。
Leha 应该计算所有 a 的 F（a） 之和，其中 a 是集合的非空子集，由所有被黑客入侵的计算机组成。形式上，让我们表示 A 从 1 到 n 的所有整数的集合。Noora要求黑客找到表达式的值。这里 F（a） 计算为所有计算机对之间距离集合 a 之间的最大值。由于所需的总和可能相当大，Noora 要求找到它的模 10^9+7。
不过，Leha太累了。因此，他无法解决这项任务。帮助黑客参加约会。
Leha decided to move to a quiet town Vickopolis, because he was tired by living in Bankopolis. Upon arrival he immediately began to expand his network of hacked computers. During the week Leha managed to get access to n computers throughout the town. Incidentally all the computers, which were hacked by Leha, lie on the same straight line, due to the reason that there is the only one straight street in Vickopolis.
Let's denote the coordinate system on this street. Besides let's number all the hacked computers with integers from 1 to n. So the i-th hacked computer is located at the point xi. Moreover the coordinates of all computers are distinct.
Leha is determined to have a little rest after a hard week. Therefore he is going to invite his friend Noora to a restaurant. However the girl agrees to go on a date with the only one condition: Leha have to solve a simple task.
Leha should calculate a sum of F(a) for all a, where a is a non-empty subset of the set, that consists of all hacked computers. Formally, let's denote A the set of all integers from 1 to n. Noora asks the hacker to find value of the ex
. Here F(a) is calculated as the maximum among the distances between all pairs of computers from the set a. Formally, 
. Since the required sum can be quite large Noora asks to find it modulo 109+7.
Though, Leha is too tired. Consequently he is not able to solve this task. Help the hacker to attend a date.
The second line contains n integers x1,x2,...,xn (1≤xi≤109) denoting the coordinates of hacked computers. It is guaranteed that all xi are distinct.
2
4 7
3
3
4 3 1
9
There are three non-empty subsets in the first sample test: . The first and the second subset increase the sum by 0 and the third subset increases the sum by 7-4=3. In total the answer is 0+0+3=3.
There are seven non-empty subsets in the second sample test. Among them only the following subsets increase the answer: . In total the sum is (4-3)+(4-1)+(3-1)+(4-1)=9.
输入格式
第一行包含一个整数 n （1≤n ≤3·10^5），表示被黑客入侵的计算机数量。
第二行包含 n 个整数 x1，x2,...,xn （1≤xi≤10^9），表示被黑客入侵的计算机的坐标。可以保证所有 xi 都是不同的。
输出格式
输出单个整数−所需的和模 10^9+7。
2 4 7
3
3 4 3 1
9
输入样例 复制
2
4 7
输出样例 复制
3数据范围与提示
第二个例子有7个非空子集。其中只有以下子集增加的不是0：{4，3}，{4，1}，{3，1}，{4，3，1}。所以答案是（4-3）+（4-1）+（3-1）+（4-1）=9。