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

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!

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.

Print the answer modulo **1000000007 (109 + 7)**.

Input | Output |
---|---|

2 3 7 | 4 |

Input | Output |
---|---|

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

75% Solution Ratio

Matrix.codeEarliest,

tuhin107494Fastest, 0.0s

fire_tornadoLightest, 393 kB

subhashis_cseShortest, 423B

Login to submit

Just solve the problem for some small sets like little oishee and see the pattern . And always reme...

Toph uses cookies. By continuing you agree to our Cookie Policy.