给一个排列 $p$，对每个 $i$，我们在平面上放置点 $(i,p_i)$。对于坐标上下限都在 $1\sim 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 $$

输入格式

第一行输入两个正整数 $n,k$。

第二行输入 $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

子任务

对于 $100\%$ 的数据，保证 $1\le n\le 10^5; 1\le k\le 3$。