数列分割ふたたび

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

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

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

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

• 入力はすべて整数

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

3
1 2 3

4

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

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

896089113