Problem Statement

There is a sequence of $N$ non-negative integers $A_1,A_2,\dots ,A_N$.

Consider forming an expression by inserting one of the $3$ kinds of operators $+,-,\times$ between each pair of adjacent $2$ terms of this sequence, and then evaluating it.
As per the usual rules, multiplication takes precedence over the other operations.

There are $3^{N-1}$ possible expressions. Find the sum of the evaluation results of all of these expressions.
Since the answer can be very large, output it modulo $10^9+7$ (it can be proved that the answer is always a non-negative integer).

Input

$N$
$A_1\ \ A_2\ \ \cdots\ \ A_N$

• $2\le N\le 2\times 10^5$
• $0\le A_i \le 10^9$
• All inputs are integers.

Output

Output the sum of the evaluation results of the possible expressions, modulo $10^9+7$.

Sample

3
1 2 3

16

5
1001 1002 1003 1004 1005

342428517