Appu doesn't like maths.He was always intimidated by its calculations and stuff.To make matters worse,his Maths teacher is very strict.He gives him tough Home Work problems to him at the end of each chapter.If Appu fails to do the homework correctly,he punishes him. Today Appu's teacher finished teaching him Set Theory,and he gave Appu the following problem:

" Lists are just like sets the only difference being that in lists a number can appear many time unlike in sets.For example {4,5,5} is a list,but not a set because 5 appears twice.But {4,5} is both a list and set.A list of size n has (2^n)-1 non-empty sublists. For example, {1,3,3} has 7 sublists : {1},{3},{3},{1,3},{3,3},1,3},{1,3,3} . Lets define sublist sum of a list as sum of all the elements in the sub-list. Lets denote sublist sums of a list S as SS[1],SS[2],SS[3]...... ,SS[ 2^n -1]. Lets also define a All Sublists Sum as ASS,

       ASS= (2^SS[1])+(2^(SS[2]) ..... + 2^(SS[2^n -1])  . Now given a list S,find the  ASS of that list. "

Looking at this statement, Appu was horrified.He has no clue whatsover on how to proceed.Can you help Appu from his punishment the next day in the class?

Input
The first line contains an integer N - the size of list S.Then next line contains N elements of list S.

Output Output the (ASS of the list S)%(10^9+7)

Constraints 1<=N<=10^5 Each element of the list can be from 0 and 10^10 (inclusive)