2780. [Codeforces 809A] 约会

【题目描述】

黑客乐哈决定搬到一个安静的小镇Vikopolis，因为他对生活在Bankopolis感到厌倦。抵达后，他立即开始扩大他的黑客网络。在这个星期里，Leha设法在整个城镇进入n台电脑。顺便说一下，被黑客乐哈入侵的所有电脑都在同一条直线上。

我们将所有被入侵的计算机的整数从1到n编号。此外，所有计算机的标号是不同的。

乐哈决心在艰苦的一周后休息一下。所以他要邀请他的朋友诺拉去一家餐馆。然而，这个IT女孩同意的唯一一个条件是：乐哈必须解决一个简单的任务。

乐哈应计算所有F(a)的总和，其中A是集合的非空子集，由所有被入侵的计算机组成。正式地，我们用A表示从1到n的所有整数的集合。诺拉要求乐哈找到表达的值。这里F（a）被计算为来自集合A的所有计算机对之间距离的最大值。由于所需的总和可以是相当大的诺拉要求它模10^9+ 7。

然而，乐哈太累了，因此他无法解决这个任务。请求你帮助乐哈解决问题。

【输入格式】

第一行包含一个整数n（1≤n≤3·10^5）表示黑客的计算机的数量。

第二行包含n整数x1，x2，...xn （1≤ xi≤10^9）入侵的计算机表示的标号。保证所有的x i是不同的。

【输出格式】

输出一个整数 - 所需要的和模10^9 ?+ 7。

【样例输入1】

2
4 7

【样例输出1】

3

【样例输入1】

3
4 3 1

【样例输出2】

9

【提示】

在例1在有三个非空的子集：{4}，{7}和{4,7}。第一和第二子集贡献增加0，第三子集贡献增加7-4 = 3。总共答案是0 + 0 + 3 = 3。

在例2中有七个非空子集。其中只有以下子集为答案提供了贡献：{4,3}，{4,1}，{3,1}，{4,3,1}。总和为（4 - 3）+（4 - 1）+（3 - 1）+（4 - 1）= 9。

【来源】

http://codeforces.com/contest/809/problem/A?