問題文

下図のような N 段のピラミッドがあり、最下段には左から順に整数 A_1, A_2, \dots, A_N が書かれています。

下の段から順に、「隣り合った 2 つの数を足した答えを上の段に書く」という操作を行ったとき、一番上に書かれる整数はいくつですか。

答えを 1000000007 (=10^9+7) で割った余りを出力してください。

制約

• 2 \leq N \leq 200000
• 1 \leq A_i \leq 10^9
• 入力はすべて整数

入力例 1

5
20 22 25 43 50

出力例 1

480

ピラミッドには以下のように整数が書かれます。よって、480 と出力すれば正解です。