/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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 で割った余りを出力せよ。
入力例 1
2 1 2
出力例 1
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 となります。
入力例 2
4 1 1 1 1
出力例 2
212
入力例 3
10 1 2 4 8 16 32 64 128 256 512
出力例 3
880971923
Score : 600 points
Problem Statement
There are N blocks arranged in a row, numbered 1 to N from left to right. Each block has a weight, and the weight of Block i is A_i. Snuke will perform the following operation on these blocks N times:
- Choose one block that is still not removed, and remove it. The cost of this operation is the sum of the weights of the blocks that are connected to the block being removed (including itself). Here, two blocks x and y ( x \leq y ) are connected when, for all z ( x \leq z \leq y ), Block z is still not removed.
There are N! possible orders in which Snuke removes the blocks. For all of those N! orders, find the total cost of the N operations, and calculate the sum of those N! total costs. As the answer can be extremely large, compute the sum modulo 10^9+7.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 ... A_N
Output
For all of the N! orders, find the total cost of the N operations, and print the sum of those N! total costs, modulo 10^9+7.
Sample Input 1
2 1 2
Sample Output 1
9
First, we will consider the order "Block 1 -> Block 2". In the first operation, the cost of the operation is 1+2=3, as Block 1 and 2 are connected. In the second operation, the cost of the operation is 2, as only Block 2 remains. Thus, the total cost of the two operations for this order is 3+2=5.
Then, we will consider the order "Block 2 -> Block 1". In the first operation, the cost of the operation is 1+2=3, as Block 1 and 2 are connected. In the second operation, the cost of the operation is 1, as only Block 1 remains. Thus, the total cost of the two operations for this order is 3+1=4.
Therefore, the answer is 5+4=9.
Sample Input 2
4 1 1 1 1
Sample Output 2
212
Sample Input 3
10 1 2 4 8 16 32 64 128 256 512
Sample Output 3
880971923