問題文

非負整数からなる $N$ 項の数列 $A_1,A_2,\dots ,A_N$ があります。

この数列の隣接する $2$ 項間のそれぞれに $+,-,\times$ の $3$ 種類の演算子のいずれかを入れて数式を作り、計算を行うことを考えます。
なお、計算は通常の規則通り、掛け算を他の演算より優先します。

あり得る数式は $3^{N-1}$ 通りありますが、その全ての数式の計算結果の総和を取った値を求めてください。
答えは非常に大きくなることがあるので $10^9+7$ で割った余りを出力してください（答えは必ず非負整数になることが証明できます）。

入力

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

• $2\le N\le 2\times 10^5$
• $0\le A_i \le 10^9$
• 入力は全て整数である。

出力

あり得る数式の計算結果の総和を $10^9+7$ で割った余りを出力してください。

サンプル

3
1 2 3

16

5
1001 1002 1003 1004 1005

342428517