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~.