Shashank is a newbie to mathematics, and he is very excited after knowing that a given l of cardinality N has (2^N - 1) non-empty sublist. He writes down all the non-empty sublists for a given set A. For each sublist, he calculates sublist_sum, which is the sum of elements and denotes them by S₁, S₂, S₃, ... , S_(2^N-1).

He then defines a special_sum, P.

P = 2^S₁ + 2^S₂ + 2^S₃ .... + 2^S_(2N-1) and reports P % (10⁹ + 7).

Input Format
The first line contains an integer N, i.e., the size of list A.
The next line will contain N integers, each representing an element of list A.

Output Format
Print special_sum, P modulo (10⁹ + 7).

Constraints
1 ≤ N ≤ 10⁵
0 ≤ a_i ≤ 10¹⁰ , where i ∈ [1 .. N]

Sample Input

3
1 1 2

Sample Output

44

Explanation

For given list, sublist and calculations are given below
1. {1} and 2¹ = 2
2. {1} and 2¹ = 2
3. {2} and 2² = 4
4. {1,1} and 2² = 4
5. {1,2} and 2³ = 8
6. {1,2} and 2³ = 8
7. {1,1,2} and 2⁴ = 16
So total sum will be 44.