You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ARC122A] Many Formulae

题面翻译

题目描述

给出长度为 $N$ 的非负整数序列 $A_1,A_2,\cdots,A_N$。

考虑在此序列的相邻 $2$ 项之间放置 + 或 - 以创建一个表达式。

有 $2^{N-1}$ 创建表达式的方法，但我们会将满足以下条件的表达式称为好表达式。

• - 不会连续出现 $2$ 次或以上。

求所有良好表达式值的总和。

可以证明，这个值始终是一个非负整数。因此，输出此值对 $10^9+7$ 取模的结果。

输入格式

输入由以下格式给出：

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

题目描述

長さ $N$ の非負整数列 $A_1,A_2,\cdots,A_N$ が与えられます．

この数列の隣接する $2$ 項の間に + または - を入れて，一つの式を作ることを考えます．

式を作る方法は $2^{N-1}$ 通りありますが，この中でも以下の条件を満たす式を，良い式と呼ぶことにします．

• - が $2$ 回以上連続で登場しない．

全ての良い式の値を足し合わせた値を求めて下さい． なお，この値はかならず非負整数となることが証明できます． そこで，この値を $10^9+7$ で割った余りを出力してください．

输入格式

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

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

输出格式

答えを $10^9+7$ で割った余りを出力せよ．

样例 #1

样例输入 #1

3
3 1 5

样例输出 #1

15

样例 #2

样例输入 #2

4
1 1 1 1

样例输出 #2

10

样例 #3

样例输入 #3

10
866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117

样例输出 #3

279919144

提示

制約

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

Sample Explanation 1

以下の $3$ 通りの良い式が考えられます．

• $3+1+5=9$
• $3+1-5=-1$
• $3-1+5=7$
• $3-1-5 =$ は - が $2$ 回以上連続で登場するため，良い式ではありません． よって，答えは $9+(-1)+7=15$ となります．

Sample Explanation 2

以下の $5$ 通りの良い式が考えられます．

• $1+1+1+1=4$
• $1+1+1-1=2$
• $1+1-1+1=2$
• $1-1+1+1=2$
• $1-1+1-1=0$
• よって答えは $4+2+2+2+0=10$ となります．

Sample Explanation 3

答えを $10^9+7$ で割った余りを出力してください．