Sum of Average

2 secs 1024 MB
hotman78

問題文


長さ の整数列 が与えられます。 の空でない連続する部分列は 個ありますが、それぞれについての平均の総和を既約分数 と表した時、 の値を で割った余りを求めてください。

制約


  • 入力は全て整数

入力


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

N
A_1 A_2 ... A_N

出力


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

入力例


3
1 2 3

出力例


12

提出


Go (1.14)