数列分割ふたたび

2 secs 1024 MB
ir_1st_vil

問題文


長さ の数列 があります。この数列をいくつかの連続部分列に分割することを考えます。このとき、分割個数を とすると 個の連続部分列 は以下の条件を満たしていなければいけません。

  • はいずれも の空でない連続部分列である。
  • をこの順序で連結すると となる。

ある分割のスコアは と定義されます。ここで の長さです。

考えられる分割方法は 通りありますが、それらすべてに対するスコアの総和を で割ったあまりを求めてください。

制約


  • 入力はすべて整数

入力



出力


答えを出力し、最後に改行してください。

入力例1

3
1 2 3
出力例1

4

考えられる分割方法は 通りです。 スコアは順に なのでそれらの総和である を出力します。

入力例2

15
986443860 261815926 135792421 423098417 667797511 192154129 543455015 87493239 690182347 484865424 916005028 320032940 811507723 438422973 753096704
出力例2

896089113

提出


Go (1.14)