Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Easy Peasy Subset Sum

Limits: 1s, 512 MB

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,

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 ≤ 105 ).
Second line contains n integers A1, A2, … , An ( 1 ≤ Ai ≤ 109 ) denoting the elements of the set.

Output

Print the answer modulo 1000000007 (109 + 7).

Samples

InputOutput
2
3 7
4
InputOutput
3
1 3 5
16

In the first case the subsets are { ( 3 ), ( 7 ), ( 3, 7 ) } . For ( 3 ) and ( 4 ) the F() is 0, and for ( 3, 7 ) it is 4. so the ans is ( 0 + 0 + 4 ) = 4

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

Author
Discussion