/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
長さ N の非負整数列 A_1,A_2,\cdots,A_N が与えられます．
この数列の隣接する 2 項の間に + または - を入れて，一つの式を作ることを考えます．
式を作る方法は 2^{N-1} 通りありますが，この中でも以下の条件を満たす式を，良い式と呼ぶことにします．
-が 2 回以上連続で登場しない．
全ての良い式の値を足し合わせた値を求めて下さい． なお，この値はかならず非負整数となることが証明できます． そこで，この値を 10^9+7 で割った余りを出力してください．
制約
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる．
N A_1 A_2 \cdots A_N
出力
答えを 10^9+7 で割った余りを出力せよ．
入力例 1
3 3 1 5
出力例 1
15
以下の 3 通りの良い式が考えられます．
-
3+1+5=9
-
3+1-5=-1
-
3-1+5=7
3-1-5 は - が 2 回以上連続で登場するため，良い式ではありません．
よって，答えは 9+(-1)+7=15 となります．
入力例 2
4 1 1 1 1
出力例 2
10
以下の 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 となります．
入力例 3
10 866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117
出力例 3
279919144
答えを 10^9+7 で割った余りを出力してください．
Score : 400 points
Problem Statement
You are given a sequence of N non-negative integers: A_1,A_2,\cdots,A_N.
Consider inserting a + or - between each pair of adjacent terms to make one formula.
There are 2^{N-1} such ways to make a formula. Such a formula is called good when the following condition is satisfied:
-does not occur twice or more in a row.
Find the sum of the evaluations of all good formulae. We can prove that this sum is always a non-negative integer, so print it modulo (10^9+7).
Constraints
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
Print the sum modulo (10^9+7).
Sample Input 1
3 3 1 5
Sample Output 1
15
We have the following three good formulae:
-
3+1+5=9
-
3+1-5=-1
-
3-1+5=7
Note that 3-1-5 is not good since- occurs twice in a row in it.
Thus, the answer is 9+(-1)+7=15.
Sample Input 2
4 1 1 1 1
Sample Output 2
10
We have the following five good formulae:
-
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
Thus, the answer is 4+2+2+2+0=10.
Sample Input 3
10 866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117
Sample Output 3
279919144
Print the sum modulo (10^9+7).