题目描述

$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$ で割った余りを求めてください。

输入格式

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

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

输出格式

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

题目大意

有 $N$ 块砖块排列成一行，从左到右编号为 $1$ 到 $N$ 。每一个砖块都有一个重量，砖块 $i$ 的重量为 $A_i$。 Snuke 会对这些 $N$ 个砖块执行如下操作：

• 选择一个还没有被移除的砖块，然后移除它。这个操作的代价是与被移除的砖块相邻的砖块（包括它自己）的重量之和。我们定义两块砖 $x$ 和 $y ~(x \leq y)$ 是相邻的，当且仅当对于所有 $z (x \leq z \leq y)$ ，砖块 $z$ 仍然没有被移除。

有 $N!$ 种移除砖块的可能顺序。你需要对于所有可能的顺序计算出移除完所有 $N$ 块砖块的代价，并计算这些代价的和。由于答案可能非常大，答案需要对 $10^9+7$ 取模。

2
1 2

9

4
1 1 1 1

212

10
1 2 4 8 16 32 64 128 256 512

880971923

提示

制約

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

Sample Explanation 1

ブロック $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$ となります。