AT_arc122_a [ARC122A] Many Formulae

[problemUrl]: https://atcoder.jp/contests/arc122/tasks/arc122_a 長さ $ 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\ \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 $ で割った余りを出力してください．