MrBon 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 S1, S2, S3, ... , S(2^N-1).

He then defines a special_sum, P.

\(P=2^{S_1}+2^{S_2}+...+2^{S_{(2^N-1)}}\)  and reports P % (10⁹ + 7).

Input:
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:
Print special_sum, P modulo (10⁹ + 7).

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