問題文

あなたは、正整数からなる長さ $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)$ に置き換える。（添字は１から振り直す。）

$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$
・入力は全て整数である。

出力

　答えを出力せよ。

サンプル

2 2
3 4

21

4 0
1 2 3 4

10

5 100000000
1000000000 999999999 888888888 777777777 666666666

870870837