SP28607 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 **A $ _{1} $** >= **A $ _{2} $** >= ... >= **A $ _{k} $** respectively. Then the descending alternating sum of array **A** is **F(A) =** **A $ _{1} $ - A $ _{2} $ + A $ _{3} $ - ... + (-1) $ ^{k+1} $ A $ _{k} $** . 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 and **|A $ _{i} $ | . You have to print the sum of the descending alternating sums of all subsets of this array **A** (there are **2** $ ^{n} $ of them) modulo **M = 10 $ ^{9} $ + 7**. In other words, if the subsets of array **A** are **S $ _{1} $ , S $ _{2,} $ ..., S $ _{2n} $** then you have to print the sum**** **F(**S $ _{1} $ ) + F(**S $ _{2} $ ) + ... + F(**S $ _{2n} $ )******** modulo **M = ****10 $ ^{9} $ + 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**.**

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 **A $ _{1} $ , A $ _{2} $ , ..., A $ _{n} $** , the elements of the array **A**.

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