問題

長さ $N$ の数列 $A_0,A_1,A_2,\cdots ,A_{N-1}$ が与えられます

要素数が $M$ ($2 \leq M \leq N+1$) であって、 各要素が $B_0\ (=0)\ <\ B_1<\ B_2<\ \cdots<\ B_{M-2}<\ B_{M+1}\ (=N)$ であるような $2^{N-1}$ 個の狭義単調増加数列 $B$ について $\prod_{i=0}^{M-1} \sum_{j=B_i}^{B_{i+1}-1} A_j$ を求め、その総和を $10^9+7$ で割ったあまりを求めなさい

より直感的には数列 $A$ の $N-1$　個の隣接要素の間に $+$ または $\times$ を挿入し、 $+$ における計算が $\times$ における計算より優先されるものとして計算した時の総和を$10^9+7$ で割ったあまりを求めなさい

制約

$1\ \leq N\ \leq\ 10^5$
$0\ \leq\ A_i\ <\ 10^9+7$

入力例1

3
1 2 3

出力例1

26

$(1\times 2\times 3)+((1+2) \times 3)+(1\times (2+3))+(1+2+3)=6+9+5+6=26$ です。