011 - 串団子

問題

様々な大きさの団子が$N$個あり、$i$番目の団子の大きさは$a_i$である。ここから$K$個の団子を選ぶ。$K$個の団子をあらゆる順番で串に刺して作ることができる、すべての串団子について考える。ただし、２つの串団子について、同じ位置にある団子の大きさがすべて同じ場合は同じものと考える。このようにして作ることができるすべての串団子について、一番大きな団子が存在する位置の和を求めて、それらの総和を求めよ。

たとえば、$N=4$個の団子それぞれの大きさが、$a_1=6,a_2=6,a_3=7,a_4=7$であり、$K=2$とする。このとき、串団子として$(6,6)、(6,7)、(7,6)、(7,7)$の４種類を作ることができる。団子の大きさの最大値が存在する位置について考えると、串団子$(6,6)$については一番大きな団子の大きさは$6$で、その団子がある位置は$1$番目と$2$番目なので、位置の和は$1+2=3$である。串団子$(6,7)$については一番大きな団子の大きさは$7$で、その位置は$2$番目なので、位置の和は$2$である。串団子$(7,6)$については一番大きな団子の大きさは$7$で、その位置は$1$番目なので、位置の和は$1$である。串団子$(7,7)$については一番大きな団子の大きさは$7$で、その位置は$1$番目と$2$番目なので、位置の和は$1+2=3$である。よって、全ての串団子の一番大きな団子が存在する位置の和の総和は、$3 + 2 + 1 + 3 = 9$である。

団子の情報と正の整数$K$が与えられたとき、上述の一番大きな団子が存在する位置の和の総和を計算するプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$N$ $K$
$a_1$ $a_2$ ... $a_N$

１行目に団子の数$N$ ($1 \leq N \leq 5000$)と取り出す団子の数$K$ ($1 \leq K \leq N$)が整数で与えられる。２行目に、各団子の大きさ$a_i$ ($1 \leq a_i \leq 1,000,000,000=10^9$)が与えられる。

出力

一番大きな団子が存在する位置の和の総和を 998,244,353 で割った余りを１行に出力する。

入出力例

入力例１

4 2
6 6 7 7

出力例１

9

入力例２

4 3
1 1 2 2

出力例２

18