問題文

茶碗蒸しくんは要素数$N$の整数列$A$を持っています。$A$の$i(1 \le i \le N)$番目の要素は$A_i$です。
$N-1$回、茶碗蒸しくんは次の操作を行います。(サンプル1を参考にしてください。)

• $i$回目の操作のとき、$A$を$(A_1+A_2,A_2+A_3,\dots,A_{N-i}+A_{N-i+1})$で置き換える

制約

• 入力は全て整数
• $2 \le N \le 100$
• $0 \le A_i \le 10^9$

入力

$N$
$A_1\ A_2\ \dots\ A_N$

$1$行目には$N$が与えられます。
$2$行目には操作前の$A$が空白区切りで与えられます。

出力

操作後の$A_1$を$10^9+7$で割った余りをを1行で出力してください。
最後に改行してください。

サンプル

4
3 10 100 1000

1333

3
0 0 0

0

5
1000000000 1000000000 1000000000 1000000000 1000000000

999999895