Problem Description

In a certain town, there lives a black cat who loves sequences and a wolf who loves calculations. Today, they decided to play by creating calculations based on a certain sequence.

The black cat has an integer sequence of length $ N $ denoted by {$ a_i $}, and they want to create expressions by inserting $ + $ or $\times$ between adjacent terms in this sequence. The wolf will then calculate the value of these expressions. Since they want to play as long as possible using this integer sequence, they decided to generate all possible expressions ($ 2^{N-1} $ in total) and find the sum of the values of these expressions.

To check if the final answer is correct, they asked you, who practices daily in programming contests, to create a program that calculates the sum of these values modulo $1,000,000,007\ (=\ 10^9\ +\ 7)$.

Please help them by creating a program that calculates this value.

Note that $\times$ has higher precedence in calculations than $ + $.

Input Format

The input is given in the following format:

$ N $ $ a_1 $ ... $ a_N $

Output Format

Output the desired answer.

Sample Input and Output

Sample Input #1

3
1 2 3

Sample Output #1

24

Sample Input #2

2
28055 35642

Sample Output #2

0

Sample Input #3

12
31415926 535897932 38462643 383279502 884197 169399375 105820974 944592307 81640628 620899862 803482534 21170679

Sample Output #3

626713706

Notes/Hints

Constraints

• $1\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ a_i\ \leq\ 10^9$ $(1\ \leq\ i\ \leq\ N)$
• $ a_i $ $(1\ \leq\ i\ \leq\ N)$ are integers.

Sample Explanation 1

The possible expressions are $ 1+2+3 $, $1+2\ \times\ 3$, $1\ \times\ 2+3$, and $1\ \times\ 2\ \times\ 3$. Calculating these expressions gives the results $ 6 $, $ 7 $, $ 5 $, and $ 6 $ respectively, so the total is $ 6+7+5+6=24 $.

Sample Explanation 2

The desired total is $1000000007\ (=\ 10^9+7)$, so output the remainder when divided by $ 10^9+7 $, which is $ 0 $.

见题面 Input 部分

见题面 Output 部分