Score : 600 points
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:
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.
Input is given from Standard Input in the following format:
N A_1 A_2 ... A_N
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.
2 1 2
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.
4 1 1 1 1
212
10 1 2 4 8 16 32 64 128 256 512
880971923