[AGC028B] Removing Blocks

有 $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$ 取模。

[problemUrl]: https://atcoder.jp/contests/agc028/tasks/agc028_b $ 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 $ で割った余りを出力せよ。

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 $ となります。