SOLVE
LATER
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 i^{th} 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$$
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.