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_{1}, S_{2}, S_{3}, ... , S(2^{N}-1).

He then defines a special_sum, P.

P = 2^{S_{1}} + 2^{S_{2}} + 2^{S_{3}} .... + 2^{S(2^{N}-1)} and reports P % (10^{9} + 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^{9} + 7).

Constraints

1 ≤ N ≤ 10^{5}

0 ≤ a_{i} ≤ 10^{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^{1} = 2

2. {1} and 2^{1} = 2

3. {2} and 2^{2} = 4

4. {1,1} and 2^{2} = 4

5. {1,2} and 2^{3} = 8

6. {1,2} and 2^{3} = 8

7. {1,1,2} and 2^{4} = 16

So total sum will be 44.

见题面

见题面