editorialで確率がどうのこうの書いてあって ??? となったので。

方針

最終的に求めたい答えは当たり前だけど $a_0 A_0 + a_1 A_1 + \cdots + a_n A_n$ の形でかける.
そして , $a_i$ の値を求めにいく.

$a_i = \displaystyle \sum_{j} ( A_j を取り除く時にA_iが連結である場合の数 )$ で求めること.
$A_j$ を取り除く時に $A_i$ が連結である場合の数を全体の $N!$ 通りの中の割合で求めること.

この二つが大きなポイントだと思う. 二つ目の方から考える.

2つ目のポイントの考察

※下記では $j \leq i$ として議論する.
$A_j$ を取り除く時に $A_i$ が連結である $\Leftrightarrow$ $A_j , \cdots , A_i$ 間で $A_j$ が最初に除かれる.
と言い換えることができる.では,その場合の数はN!のうちどのくらいの割合なのか?

$A_j \cdots A_i$ 間で,初めて取り除かれるものを $A_k$ とし , これによって事象を定義する.
すなわち , 全事象 $\Omega = \displaystyle \bigcup_{k=j}^i \left\{ 事象k ; A_j \cdots A_i 間でA_kが初めて除かれる \right\}$
これらは排反の事象であり , 確率(場合の数の割合)はどの事象も等しく $P(k) = \dfrac{1}{i - j + 1}$ となっている.

$A_j$ が最初に除かれる場合の数を知りたかったので, 全体の場合の数をかけて

$N! P(j) = \dfrac{N!}{i - j + 1}$

あと , $j \leq i$ と条件を取っ払えば

$N! P(j) = \dfrac{N!}{|i - j| + 1}$

1つ目のポイントの考察

あとはさっきの結果を代入してあげればok

$a_i = \displaystyle \sum_{j} \dfrac{N!}{|i - j|+ 1}$

最後にもう一工夫.
$0 \leq |i-j| \leq N$ より , $\displaystyle \sum_{k = 0}^N \dfrac{N!}{k+ 1}$ を先に計算(累積和)しておくことができる. $O(N)$
すると $a_i$ が $O(1)$ で求まるようになる.

なので,全体は答え $a_0 A_i + a_1 A_1 + \cdots + a_n A_n$ は $O(N)$ で求まる.

ソースコード

N = int(input())
A = list(map(int,input().split(" ")))
mod = 10**9+7

# N!計算
fact = 1
for i in range(2,N+1):
    fact *= i
    fact %= mod

# 場合の数計算
rev = [ (pow((i),mod-2,mod)*fact)%mod for i in range(1,N+1) ]
# 累積和
for i in range(N-1):
    rev[i+1] += rev[i]
    rev[i+1] %= mod

# a_0 A_0 + a_1 A_1 + ... + a_n A_n を計算
ans = 0
for i in range(N):
    ans += A[i] * (rev[i] + rev[N-1-i] - rev[0]) % mod
    ans %= mod

print(ans)