順列 $p$ が与えられます。各 $i$ に対して、平面上に点 $(i, p_i)$ を配置します。座標の上下限がともに $1$ から $n$ の範囲内にあるすべての $\left(\frac{n(n+1)}{2}\right)^2$ 通りの矩形について、各矩形に含まれる点の個数の $k$ 乗の総和を求めてください。

形式的には、以下の値を計算してください。

$$ \sum_{1\le l\le r\le n} \sum_{1\le d\le u\le n} \left|\left\{ i\mid l\le i\le r \land d\le p_i\le u \right\}\right|^k $$

入力

1行目に2つの正整数 $n, k$ が与えられます。

2行目に $n$ 個の正整数、すなわち順列 $p$ が与えられます。

出力

答えを出力してください。答えは非常に大きくなる可能性があるため、$998244353$ で割った余りを出力してください。

入出力例

入力 1

10 1
2 1 10 3 5 9 4 7 6 8

出力 1

4948

入力 2

10 2
2 1 10 3 5 9 4 7 6 8

出力 2

16614

入力 3

10 3
2 1 10 3 5 9 4 7 6 8

出力 3

74224

小課題

すべてのデータにおいて、$1\le n\le 10^5; 1\le k\le 3$ を満たします。