DALTSUM - Descending Alternating Sums

Given an array A of k integers (not necessarily distinct), we define the descending alternating sum of this array, denoted F(A) the following way. First, we sort the array in descending order. Suppose the elements, after sorting, are A1A2 ≥ ... ≥ Ak respectively. Then the descending alternating sum of array A is

F(A) = A1 - A2 + A3 - ... + (-1)k+1 Ak.

For example, if A = [5, -3, 8, 2, 0, -5] then after sorting it in descending order, we find A = [8, 5, 2, 0, -3, -5]. So the descending alternating sum of this array is 8 - 5 + 2 - 0 + (-3) - (-5) = 7. In particular, the descending alternating sum of an empty array is 0.

You are given an array A of n integers where 1 ≤ n ≤ 105 and |Ai| ≤ 1018. You have to print the sum of the descending alternating sums of all subsets of this array A (there are 2n of them) modulo M = 109 + 7. In other words, if the subsets of array A are S1, S2, ..., S2n then you have to print the sum

F(S1) + F(S2) + ... + F(S2n) modulo M = 109 + 7.

Note: we consider some integer modulo a positive integer to be non-negative. In the other words, the output R must satisfy the inequality 0 ≤ R < M.

Input

The first line of the input file contains a single integer n, denoting the size of the array A.

The second line contains n integers A1, A2, ..., An, the elements of the array A.

Output

Print a single integer, the sum of descending alternating sums of all subsets of the array A.

Example

Input:
3
-1 9 3
Output: 36

Added by:AlphaQ
Date:2016-10-06
Time limit:0.300s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Self posed

hide comments
2017-05-17 17:39:49 Shubham Jadhav
Piece Of Cake if you figure out the solution @Mangesh
2016-10-09 18:36:11
if some elements are same,then no. of subsets wont be equal to pow(2.n), right ??

Reply: No. By subset I meant mathematical subset, i.e. a subsequence. The number of subsets of an array of size n is always 2^n.

Last edit: 2016-10-10 10:06:26
2016-10-08 12:04:09
Pen Paper + Modular Exponentiation = AC :)
2016-10-07 03:00:24
@tasmeemreza এখানে ও ok ok করা শুরু করছও ... o.O

Last edit: 2016-10-07 03:01:59
2016-10-07 02:01:43 :D
I'm pretty sure there are exactly 0 corner cases for this problem. The only thing to remember is that you need to have result in range <0;MOD). Modulo result can be negative. In C/C++, for example, you should do something like this:
a %= MOD;
if (a < 0) a += MOD;

Last edit: 2016-10-07 02:53:41
2016-10-06 19:31:19
tasmeemreza please give testcase for corner case
2016-10-06 17:01:42
ok
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.