No.797 Noelちゃんとピラミッド

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 191
作問者 : Lemma299Lemma299 / テスター : Kutimoti_TKutimoti_T
9 ProblemId : 2104 / 出題時の順位表
問題文最終更新日: 2019-03-18 00:25:57

問題文

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

  • 隣り合う数の和を順に並べ,新しく長さ $N - 1$ の数列を新しく作る.
これを繰り返すとやがて長さは $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 行に出力してください.

サンプル

サンプル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
サンプル2
入力
11
1 3 3 3 5 7 5 3 3 3 1
出力
4916
サンプル3
入力
15
63 93 23 32 87 15 32 19 57 43 47 95 51 93 13
出力
638367

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。