配点 : $600$ 点

問題文

$N$ 個のブロックが一列に並んでおり、左から右へ順に $1$ から $N$ の番号がついています。 それぞれのブロックには重さが定まっており、ブロック $i$ の重さは $A_i$ です。 すぬけ君は、これらのブロックに対して次の操作を $N$ 回行います。

• まだ取り除かれていないブロックを $1$ つ選んで取り除く。 この操作のコストは、取り除くブロックと連結なブロック（取り除くブロック自身も含む）の重さの総和となる。 $2$ つのブロック $x$, $y$ ( $x \leq y$ ) が連結であるとは、すべての $z$ ( $x \leq z \leq y$ ) について、ブロック $z$ が取り除かれていないことを意味する。

ブロックを取り除く順番はちょうど $N!$ 通りあります。 $N!$ 通りのすべての順番について $N$ 回の操作のコストの合計を求め、その総和を求めてください。 ただし、答えは非常に大きくなることがあるので、$10^9+7$ で割った余りを求めてください。

制約

• $1 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_1$ $A_2$ $...$ $A_N$

出力

$N!$ 通りのすべての順番について $N$ 回の操作のコストの合計を求め、その総和を $10^9+7$ で割った余りを出力せよ。

2
1 2

9

ブロック $1$, $2$ の順で取り除く場合を考えます。 まず、最初の操作では、ブロック $1$ と $2$ が連結なので、操作のコストは $1+2=3$ です。 次の操作では、ブロック $2$ しか残っていないので、操作のコストは $2$ です。 よって、この順で取り除く場合のコストの合計は $3+2=5$ です。

ブロック $2$, $1$ の順で取り除く場合を考えます。 まず、最初の操作では、ブロック $1$ と $2$ が連結なので、操作のコストは $1+2=3$ です。 次の操作では、ブロック $1$ しか残っていないので、操作のコストは $1$ です。 よって、この順で取り除く場合のコストの合計は $3+1=4$ です。

上記より、答えは $5+4=9$ となります。

4
1 1 1 1

212

10
1 2 4 8 16 32 64 128 256 512

880971923