Sum of Average

2 secs 1024 MB
hotman78's icon hotman78

問題文

長さ NN の整数列 A1,...,ANA_1,...,A_N が与えられます。 AA の空でない連続する部分列は N(N+1)/2N(N+1)/2 個ありますが、それぞれについての平均の総和を既約分数 PQ\frac{P}{Q} と表した時、P×Q109+5P\times Q^{10^9+5} の値を 109+710^9+7で割った余りを求めてください。

制約

  • 1N5×1041 \leq N \leq 5 \times 10^4
  • 0Ai<1090 \leq A_i < 10^9
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 ... A_N

出力

Aの空でない連続する部分列の平均の総和を 109+710^9+7 で割った余りを求めてください。

入力例

3
1 2 3

出力例

12

Submit


Go (1.21)