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

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 140
作問者 : NoelちゃんNoelちゃん / テスター : Kutimoti_TKutimoti_T
7 ProblemId : 2104 / 出題時の順位表

問題文

ある日 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
提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。