You are given an array of $N$ integers, $a_1,a_2,\dots ,a_N$. Find the sum of all of its subsequence sums modulo ${10}^9+7$.

Constraints

$1\le N\le {10}^6$

$1\le a_i\le {10}^9$

Input Specification

The first line contains an integer, $N$.

The next line contains $N$ space-separated integers, $a_1,a_2,\dots ,a_N$.

Output Specification

Output the sum of all subsequence sums modulo ${10}^9+7$.

Sample Input

3
1 2 3

Sample Output

24

Explanation for Sample

The subsequence sums are

• $1=1$
• $1+2=3$
• $1+3=4$
• $1+2+3=6$
• $2=2$
• $2+3=5$
• $3=3$

The sum of all subsequence sums is $1+3+4+6+2+5+3=24$.