Easy Peasy Subset Sum

Little Oishee loves to watch TV. But her mother, who is a math teacher, doesn't like this at all. She thinks this way her daughter is being spoiled. So, she gave her this homework to keep her away from watching too much TV.

Let's define a function,

$F(S) = \sum_{i=1}^{n}\sum_{j=i+1}^{n} \left | A_{i} - A_{j} \right |$

Now, given a set $S$ with $n$ integers, she needs to find the cumulative sum of $F(a)$ for all $a$, where $a$ is any non-empty subset of $S$.

Little Oishee who is very clever took a paper and pen and tried this for some random small sets and thought this wasn't difficult. So, she went to her mother and told her "Ammu etato easy peasy." Her mother laughed at her and gave her some big sets of numbers and said "Ok dear, finish these easy peasy home works first then you may go and watch TV".

Then the little one realized, this wasn't as easy as she thought. ICC Champions Trophy is going on. Little Oishee is really fond of cricket and doesn't want to miss even a single match. So, as always she got depressed and sat on her bed with a sad face. Now, you are her friend and a cunning computer programmer. Can you do this task on behalf of little Oishee? Then both of you can enjoy the match together!

Input

The first line contains one integer $n$ ($1 ≤ n ≤ 10^5$).

Second line contains $n$ integers $A_1$, $A_2$, ..., $A_n$ ($1 ≤ A_i ≤ 10^9$) denoting the elements of the set.

Output

Print the answer modulo $1000000007$ ($10^9 + 7$).

Samples

Input	Output
2 3 7	4
In the first case the subsets are $\{ ( 3 ), ( 7 ), ( 3, 7 ) \}$. For $( 3 )$ and $( 7 )$ the $F()$ is 0, and for $( 3, 7 )$ it is 4. So the answer is $( 0 + 0 + 4 ) = 4$.

Input	Output
3 1 3 5	16
In the second case the subsets (with at least size greater than 1) are $\{ ( 1, 3 ) , ( 1, 5 ), ( 3, 5 ) , ( 1, 3, 5 ) \}$ answer the $F()$ value for them are $(2 + 4 + 2 + 8) = 16$.