Happy and Sets
Tag(s):

## Combinatorics, Easy, Math

Problem
Editorial
Analytics

Once Happy was playing with his friends during his maths class. Seeing this, his teacher asked him to solve a problem. The teacher gave him a set of n positive integers and asked him to tell the sum of the product of elements of all the possible subsets.

For e.g. Say, the teacher gave him a set {$2$, $3$, $5$}. The possible subsets of this set are {$2$}, {$3$}, {$5$}, {$2$, $3$}, {$2$, $5$}, {$3$, $5$} and {$2$, $3$, $5$}. So Happy should report the answer as the sum of $2$, $3$, $5$, $6$ ($2$ * $3$), $10$ ($2$ * $5$), $15$ ($3$ * $5$) and $30$ ($2$ * $3$ * $5$) i.e., $71$ to the teacher.

As the output of the problem can be large, so the teacher asked happy to report the answer modulo $10^9$+$7$ ($1000000007$).

INPUT:

The first line of input contains an integer n denoting the number of elements in the set and the next line consists of n space separated integers. The ith integer is denoted by a_i.

OUTPUT:

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

Constraints:

$1$ ≤ n ≤ $10^5$
$0$ ≤ a_i ≤ $10^7$

SAMPLE INPUT
3
2 3 5
SAMPLE OUTPUT
71
Explanation

For sample input, the set consists of 3 integers 2, 3 and 5. The possible subsets of this set are {2}, {3}, {5}, {2, 3}, {2, 5}, {3, 5} and {2, 3, 5}. The product of elements of the subsets are 2, 3, 5, 6, 10, 15 and 30. The sum of these products is 71. So the answer is 71%(10^9+7) = 71.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

February Clash '17

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Number Theory
• Algorithms > Graphs
• Algorithms > Dynamic Programming