問題文

$N$項からなる正整数列$A$が与えられます．

この数列の隣接する$2$項の間に+または-を入れて， 1つの式を作ることを考えます．式を作る方法は$2^{N-1}$通りありますが，そのすべての式の計算結果の和を求めてください．

答えの絶対値は非常に大きくなることがあるので，求める答えを$X$とすると，$X \equiv Y (\mathbf{mod}10^9+7)$を満たす $0 \leq Y \leq 10^9+6$を出力してください．

制約

• $1 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$
• 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられます．

出力

答えを$1$行に出力せよ．

サンプル

3
3 1 4

12

考えられる式を作る方法は

• $3+1+4$
• $3-1+4$
• $3+1-4$
• $3-1-4$

の$4$通りです． また，それぞれの計算結果は$8,6,0,-2$であるのでその和である$12$を出力します．

10
271 828 182 84 590 45 235 36 28 74

138752