AT_agc028_b [AGC028B] Removing Blocks

[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

N/A

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