長さ の数列 があります。この数列をいくつかの連続部分列に分割することを考えます。このとき、分割個数を とすると 個の連続部分列 は以下の条件を満たしていなければいけません。
ある分割のスコアは と定義されます。ここで は の長さです。
考えられる分割方法は 通りありますが、それらすべてに対するスコアの総和を で割ったあまりを求めてください。
答えを出力し、最後に改行してください。
3 1 2 3
4
考えられる分割方法は の 通りです。 スコアは順に なのでそれらの総和である を出力します。
15 986443860 261815926 135792421 423098417 667797511 192154129 543455015 87493239 690182347 484865424 916005028 320032940 811507723 438422973 753096704
896089113