Contest Duration: - (local time) (120 minutes) Back to Home
A - Many Formulae /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

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

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

### 制約

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

### 入力

N
A_1 A_2 \cdots A_N


### 入力例 1

3
3 1 5


### 出力例 1

15


• 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


• 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


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

### 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).