問題文

ある町に、数列が大好きな黒猫と計算が大好きな狼が住んでいます。今日は、二人である数列をもとに計算をして遊ぶことにしました。

黒猫は、長さ $N$ の整数列 {$a_i$} を持っていて、この数列の隣り合う項の間に $+$ または $\\times$ を挿入した式を作り、狼がその値を計算しようとしています。 二人はこの整数列を使いできるだけ長く遊びたいので、作ることができる全ての式 ($2^{N-1}$ 通りある) を作り、それらの式の値の合計を求めることにしました。

最終的に答えが合っているかどうかをチェックしたいので、二人はこれらの合計を $1,000,000,007 (= 10^9 + 7)$ で割ったあまりを求めるプログラムを作ることを、プログラミングコンテストで日々鍛錬を続けているあなたに頼んできました。

あなたはこの値を計算するプログラムを作ることで、二人を助けてください。

ただし、 $\\times$ は $+$ よりも計算の優先順序が高いことに注意してください。

制約

• $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)$ は整数である。

入力

入力は以下の形式で与えられる。

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

出力

求める答えを出力せよ。

入力例 1

3
1 2 3

出力例 1

24

考えられる数式は、 $1+2+3$ と $1+2 \\times 3$ と $1 \\times 2+3$ と $1 \\times 2 \\times 3$ の $4$ 種類です。 これらの式を計算すると、それぞれ答えは $6$、$7$、$5$、$6$ となるので、合計は $6+7+5+6=24$ です。

入力例 2

2
28055 35642

出力例 2

0

求める合計は $1000000007 (= 10^9+7)$ となるので、これを $10^9+7$ で割ったあまりである $0$ を出力します。

入力例 3

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

出力例 3

626713706