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 A_i 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⁹+7.

Input format

The first line contains a single integer N.

The second line contains N non-negative integers A₁, A₂, ..., A_N.

Output format

In a single line print modulo 10⁹+7 the sum of total scores of possible remaining sequences.

Constraints

1 ≤ N ≤ 200,000
0 ≤ A_i ≤ 10⁹

Subtasks

Extra constraints	Points	Tests
N ≤ 15	10	1-2
N ≤ 200	20	3-4
N ≤ 4000	30	5-7
no extra constraints	40	8-11