問題一覧 > 通常問題

No.1102 Remnants

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / 通常問題
タグ : / 解いたユーザー数 136
作問者 : eSeFeSeF / テスター : 37zigen37zigen
23 ProblemId : 4283 / 出題時の順位表
問題文最終更新日: 2020-07-03 23:42:36

問題文

あなたは、正整数からなる長さ $N$ の数列 $A=(A_1,\dots ,A_N)$ を持っています。 これに対して、以下の操作を $K$ 回行います。

・操作時点での数列を $B=(B_1,\dots ,B_M)$ とする。
 $1\le l\le r\le M$ を満たす整数 $l,\ r$ を自由に選び、持っている数列を部分列 $(B_l,B_{l+1},\dots ,B_r)$ に置き換える。(添字は1から振り直す。)

$K$ 回の一連の操作のスコアを、操作が全て終了した時点での数列の要素の総和と定義します。
考えうる全ての操作手順についてスコアを求め、その合計を $10^9+7$ で割ったあまりを出力してください。

なお、2つの操作手順が異なるとは、ある正整数 $i$ が存在して、 $i$ 回目の操作で選ぶ整数の組 $(l,\ r)$ が異なることを言います。

入力

$N\ \ K$
$A_1 \ \ \dots \ \ A_N$

【制約】
・$1\le N\le 2\times 10^5$
・$0\le K\le 10^8$
・$1\le A_i\le 10^9$
・入力は全て整数である。

出力

 答えを出力せよ。

サンプル

サンプル1
入力
2 2
3 4
出力
21

1回目の操作では、数列は $(3,4),\ (3),\ (4)$ のいずれかになります。
2回目の操作では、$(3,4)$ からは $(3,4),\ (3),\ (4)$ のいずれかに変化します。 $(3)$ からは $(3)$、$(4)$ からは $(4)$ に変化します。
以上より、スコアの総和は $7+3+4+3+4=21$ です。

サンプル2
入力
4 0
1 2 3 4
出力
10

操作を行わないので、操作手順は1通りしかなく、スコアの総和は $10$ です。

サンプル3
入力
5 100000000
1000000000 999999999 888888888 777777777 666666666
出力
870870837

総和は非常に大きくなることがあるので、$10^9+7$ で割ったあまりを出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。