Codeforces Round #415 (Div. 1) A. Do you want a date?

Leha decided to move to a quiet town Vičkopolis, 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 Vičkopolis.

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 expression $\text{[math]}$ . Here F(a) is calculated as the maximum among the distances between all pairs of computers from the set a. Formally, $\text{[math]}$ . 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.

Input

The first line contains one integer n (1 ≤ n ≤ 3·105) denoting the number of hacked computers.

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.

Output

Print a single integer — the required sum modulo 109 + 7.

Examples

input

2
4 7

output

input

3
4 3 1

output

Note

There are three non-empty subsets in the first sample test: $\text{[math]}$ , $\text{[math]}$ and $\text{[math]}$ . The first and the second subset increase the sum by 0and 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: $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ . In total the sum is (4 - 3) + (4 - 1) + (3 - 1) + (4 - 1) = 9.

题意概括：给出一个无重集合A，求A的所有子集极差的和

挺有意思的数学题

先对A排序，然后不妨枚举子集的最小元素，看一下它对答案的贡献

考虑一个数列1 3 5 7 9，假设1是子集的最小元素

再考虑集合的最大元素，假设是3，那么5 7 9都不能选，总共1种情况，对答案贡献是1x2

假设是5，那么3随便选不选，7和9不能选，总共2种情况，对答案贡献是2x4

假设是7，那么3和5随便选不选，9不能选，总共4种情况，对答案贡献是4x6

看出规律了吧？每一个元素j对最小元素i的贡献是$ (x[j]-x[i])*2^{j-i+1} $ 现在我们需要快速求这个东西的后缀和

事实上维护一下 $ sum{x[i]*2^{i-1}} $ 的前缀和，然后做一下区间减就足够解决这个问题了

解释一下，第一个循环求前缀和，第二个循环做区间减，然后除掉多余的2的幂次，然后再减去x[i]这个起点不是0对答案的影响

 1 #include <iostream>
 2 #include <cstdlib>
 3 #include <cstdio>
 4 #include <algorithm>
 5 #include <string>
 6 #include <cstring>
 7 #include <cmath>
 8 #include <map>
 9 #include <stack>
10 #include <set>
11 #include <vector>
12 #include <queue>
13 #include <time.h>
14 #define eps 1e-7
15 #define INF 0x3f3f3f3f
16 #define MOD 1000000007
17 #define rep0(j,n) for(int j=0;j<n;++j)
18 #define rep1(j,n) for(int j=1;j<=n;++j)
19 #define pb push_back
20 #define mp make_pair
21 #define set0(n) memset(n,0,sizeof(n))
22 #define ll long long
23 #define ull unsigned long long
24 #define iter(i,v) for(edge *i=head[v];i;i=i->nxt)
25 #define max(a,b) (a>b?a:b)
26 #define min(a,b) (a<b?a:b)
27 #define print_runtime printf("Running time:%.3lfs
",double(clock())/1000.0)
28 #define TO(j) printf(#j": %d
",j);
29 //#define OJ
30 using namespace std;
31 const int MAXINT = 300010;
32 const int MAXNODE = 100010;
33 const int MAXEDGE = 2 * MAXNODE;
34 char BUF, *buf;
35 int read() {
36     char c = getchar(); int f = 1, x = 0;
37     while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
38     while (isdigit(c)) {x = x * 10 + c - '0'; c = getchar();}
39     return f * x;
40 }
41 char get_ch() {
42     char c = getchar();
43     while (!isalpha(c)) c = getchar();
44     return c;
45 }
46 //------------------- Head Files ----------------------//
47 
48 int a[MAXINT], n;
49 ll b[MAXINT];
50 ll ans, con;
51 ll pw(ll b, ll u) {
52     ll ans = 1;
53     if (u < 0) return -1;
54     for (; u; u >>= 1, b = b * b % MOD) if (u & 1) ans = ans * b % MOD;
55     return ans;
56 }
57 void get_input();
58 void work();
59 int main() {
60     get_input();
61     work();
62     return 0;
63 }
64 void work() {
65     for (int i = 1; i < n; i++) {
66         b[i] = (b[i - 1] + a[i] * pw(2, i - 1)) % MOD;
67     }
68     for (int i = 0; i < n - 1; i++) {
69         ans = ((ans + (b[n - 1] - b[i]) * pw(pw(2, i), MOD - 2) - a[i] * (pw(2, n - i - 1) - 1)) % MOD + MOD ) % MOD;
70     }
71     printf("%lld
", ans);
72 }
73 void get_input() {
74     n = read();
75     rep0(i, n) a[i] = read();
76     sort(a, a + n);
77 }