← 返回题目列表

Codeforces · 809/A

A. 你想约会吗?

中文机器翻译题面 查看原题

Leha 决定搬到一个安静的小镇 Vičkopolis,因为他厌倦了在 Bankopolis 的生活。抵达后,他立即开始扩大他的被黑客入侵的计算机网络。在这一周里,Leha 设法访问了全镇的 n 台计算机。顺便说一句,所有被 Leha 黑客攻击的计算机都位于同一条直线上,因为维克科波利斯只有一条直街。

让我们表示这条街道上的坐标系。此外,我们用 1 到 n 的整数对所有被黑客攻击的计算机进行编号。所以第 i 台被黑客入侵的计算机位于 xi 点。此外,所有计算机的坐标都是不同的。

Leha 决定在辛苦的一周后好好休息一下。因此他打算邀请他的朋友Noora去一家餐馆。然而女孩同意去约会,只有一个条件:莱哈必须解决一项简单的任务。

Leha 应该计算所有 a 的 F(a) 之和,其中 a 是由所有被黑客攻击的计算机组成的集合的非空子集。形式上,我们将 A 表示为从 1 到 n 的所有整数的集合。 Noora 要求黑客查找表达式 $$\sum_{a \subseteq A, a \neq \varnothing} F(a)$$ 的值。这里,F(a) 被计算为集合 a 中所有计算机对之间的距离中的最大值。形式上,$${\displaystyle F(a)=\max _{i,j\in a}|x_{i}-x_{j}|}$$。由于所需的总和可能相当大,Noora 要求对 109 + 7 求模。

不过,Leha 太累了。因此他无法解决这个任务。帮助黑客参加约会。

输入

第一行包含一个整数n (1 ≤ n ≤ 3·105),表示被黑客攻击的计算机数量。

第二行包含 n 个整数 x1, x2, ..., xn (1 ≤ xi ≤ 109) 表示被黑计算机的坐标。保证所有 xi 都是不同的。

输出

打印一个整数——所需的模 109 + 7 的总和。

示例

输入 #1

2
4 7

输出 #1

3

输入 #2

3
4 3 1

输出 #2

9

注意

第一个样本测试中有三个非空​​子集:$$\{4\}$$、$$\{7\}$$ 和 $${ \{ 4, 7 \} }$$。第一个和第二个子集使总和增加 0,第三个子集使总和增加 7 - 4 = 3。总的答案是 0 + 0 + 3 = 3。

第二个样本测试中有七个非空子集。其中只有以下子集增加了答案:$${\left\{4,3\right\}}$$、$${\{4,1\}}$$、$${ \left\{ 3, 1 \right\} }$$、$${\{4,3,1\}}$$。总和为 (4 - 3) + (4 - 1) + (3 - 1) + (4 - 1) = 9。