問題文

ある日 Noel ちゃんは長さ $N$ の数列を見つけました，この数列に対し Noel ちゃんは次の操作を考えます．

• 隣り合う数の和を順に並べ，新しく長さ $N - 1$ の数列を新しく作る．

入力

$N$
$a_1\ \ a_2\ \cdots\ a_{N-1}\ \ a_N$

1 行目に元の数列の長さ $N(1\le N\le 10^5)$ が与えられます．
2 行目に元の数列の要素 $a_i(0\le a_i\le 10^9)$ が空白区切りで与えられます．

出力

最終的な数列の要素を $10^9+7$ で割った余りを 1 行に出力してください．

サンプル

5
1 2 3 4 5

48

1. 1 2 3 4 5
2. 3 5 7 9
3. 8 12 16
4. 20 28
5. 48

11
1 3 3 3 5 7 5 3 3 3 1

4916

15
63 93 23 32 87 15 32 19 57 43 47 95 51 93 13

638367