問題文

ある日、ミツバチ君は以下のような問題を思いつきました。

Divide Card

カードが$\ N\ $枚重なった山が最初一つあり、この山の上から$\ i\ $番目のカードには$\ A_i\ $という整数が書かれています。
また、あなたは変数$\ S\ $を持っており、現在は$\ S=0\ $です。


あなたは今からちょうど$\ K\ $回、以下の操作を繰り返します。ここで$\ 1 \leq K < N\ $が成立しています。


カードを$\ Z\ $枚$\ (2\leq Z)\ $含む山を一つ選び、これを$\ P\ $とします。$\ P\ $の上から$\ t\ $枚$\ (1\leq t \leq Z-1)\ $を順序を保って分割した山を$\ Q\ $とし、残った$\ Z-t\ $枚の山を新しく$\ P\ $とします。
分割が終了した時点で$\ P\ $が含むカードに書かれた数字の総和を$\ X\ $、$\ Q\ $が含むカードに書かれた数字の総和を$\ Y\ $として、$\ S\ $に$\ X \times Y\ $を加算します。


操作としてありえるのは$\ (N-1) \times (N-2) \times \cdots \times (N-K)\ $通りありますが、その全てにおいて操作後の$\ S\ $を足し合わせた値を求めてください。


ただし、$2\ $つの$\ K\ $回の操作が異なるとは、$i\ $回目の操作後に以下が成り立つような整数$\ i(1 \leq j \leq K)\ $が存在することとします。


一方ではもともと上から$\ l\ $番目にあったカードと$\ m\ $番目にあったカードが同じ山にあり、もう一方では同じ山にないような整数$\ l,m(1 \leq l < m \leq N)\ $が存在する。

しかし、ミタルシ君にとってこれは簡単すぎたので、以下のような変更がなされました。

Mitarushi's Remodeling

整数$\ N^\prime ,K^\prime\ $と$\ N^\prime\ $個の正の整数$\ M_1,M_2, \cdots ,M_{N^\prime}\ $が与えられます。
「$\ N=N^\prime\ $かつ$\ 1 \leq K \leq K^\prime\ $かつ$\ 1\ $以上$\ N^\prime\ $以下の全ての整数$\ i\ $に対し$\ 1 \leq A_i \leq M_i\ $」が満たされるようなDivide Cardの入力は$\ K^\prime \times M_1 \times M_2 \times \cdots \times M_{N^\prime}\ $通りありますが、その全てに対してDivide Cardの答えを足し合わせた値を求めてください。


ただし、答えは大きくなることがあるので、$\ 998244353\ $で割った余りを出力してください。

Mitarushi's Remodelingを解いてください。

入力

$N^\prime\ \ K^\prime$
$M_1\ \ M_2\ \ \cdots \ \ M_{N^\prime}$

• $1 \leq K^\prime < N^\prime \leq 5\times 10^5$
• $1 \leq M_i \leq 10^9(1 \leq i \leq N^\prime)$
• 入力は全て整数

出力

Mitarushi's Remodelingの答えを出力し、最後に改行してください。$\ 998244353\ $で割った余りを出力することに注意してください。

サンプル

3 1
1 1 2

11

7 6
20 21 2 10 2 11 76

249962858

10 7
31415 92653 58979 32384 62643 38327 95028 84197 16939 93751

666468393