Happy and Sets

4.2

29 votes
Approved, Combinatorics, Easy, Math
Problem

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 109+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 109+7 (1000000007).

Constraints:

1n105
0a_i107

Sample Input
3
2 3 5
Sample Output
71
Time Limit: 1
Memory Limit: 256
Source Limit:
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.

Editor Image

?