解法
まず, とても愚直な方法を試すと, おそらく
の計算量になると思います(next_permutationを用いて取り出す順番を決め,(O(N!)), 一つ取り出すごとに隣接するブロックのコストを合算する計算(O(N))をO(N)回ほど繰り返すので.). 制約をみると, とても愚直な方法は間に合いそうにありません.
そこで, 『あるブロックのコストが何回足されるか』に着目してみます.
ある位置のブロックのコストが何度足されるかだけを考え, 後で掛けあわせます.
あるブロックというものを
番目のブロックとしておきましょう.
このブロックのコストが合算されるときは, ある
番目のブロックを抜いたときの, 次のような場合のときです.
- 番目のブロックを取り除くとき.
- 番目(
)のブロックを取り除いたとき, 
~ までのブロックが取り除かれていないとき.
- 番目(
)のブロックを取り除いたとき, 
~ までのブロックが取り除かれていないとき.
以上の3つの場合があります.
それぞれの場合が, どれだけ
に含まれているかを考察します.
まず, 1の場合を考えてみましょう.
この場合は簡単で, どの取り除き方にしても 最終的にすべてのブロックを取り除くことになるため, 通りの場合が存在することがわかります.
2の場合を考えてみましょう.
ある番目のブロックを取り除いたとき, 番目までブロックが取り除かれていない, ということは『番目から番目までのブロックの中で, はじめて取り除くのが番目のブロックである』ということと同値です.
そこで,
『通りある取り除き方のうち, 〜までの
個のブロックの中で初めて取り除くのが番目のブロックである場合の数はいくつか？』を考えることができます.
取り除き方が一様であることを加味すると, この場合の数は
となることがわかります.
言い方を変えると, 『通りある取り除き方のうち, 〜までの個のブロックの中で初めて取り除くのが番目のブロックである取り除き方の割合は
である.』とも言えます.(公式ではそのような解説でした.)
2がわかると3も同様で, こちらも場合の数は
となります.
以上により, 各
について1,2,3を合算すると
の解法を得ることができます. 具体的には, あるについて, を
まで回してブロックの足される回数を数えたあと, 
を掛けあわせ, 答えに足し合わせる, ということします.
計算をする際は, フェルマーの小定理で逆元を計算して掛け算をしましょう.
を
にするには, ブロックの足される回数の割合が規則的であること(単純に分母が1ずつ減ったり増えたりしています)を利用して, 
でブロックの足される回数を数えることができるように逆元の累積和(
)を取っておけばよいです.
答えはMODをとっているので, あくまで逆元の累積和であることに注意してください (割り算を掛け算で実装する必要があります. )
