Limak is an old brown bear.
He often goes bowling with his friends.

For rolling a ball one gets a score - a non-negative integer number of points.
Score for the i-th roll is multiplied by i and scores are summed up.
For example, for rolls with scores 7, 10, 5 the total score is equal to 7×1 + 10×2 + 5×3 = 42.

Limak made N rolls and got a score Ai for the i-th of them.

Unfortunately, the bowling club's computer system isn't stable today.
Any rolls can be erased!
Then, the total score is calculated as if there were only non-erased rolls.
There are 2^N possible sequences of remaining (non-erased) rolls.
Limak is curious about various statistics of this situation.

He asks you for one thing.
Find the sum of total scores of all 2^N possible sequences of remaining rolls.
Print it modulo 10^9+7.

Input format
The first line contains a single integer N.

The second line contains N non-negative integers A1, A2, ..., AN.

Output format
In a single line print modulo 10^9+7 the sum of total scores of possible remaining sequences.

Constraints
1 ≤ N ≤ 200,000
0 ≤ Ai ≤ 10^9

SAMPLE INPUT
3
6 12 8

SAMPLE OUTPUT
160

Explanation

There are eight possible remaining subsequences.

{} - 0
{6} - 6
{12} - 12
{8} - 8
{6, 12} - 30
{6, 8} - 22
{12, 8} - 28
{6, 12, 8} - 54

0 + 6 + 12 + 8 + 30 + 22 + 28 + 54 = 160

见题面

见题面