Given a permutation $p$, for each $i$, we place a point $(i, p_i)$ on a plane. For all $\left(\frac{n(n+1)}{2}\right)^2$ possible rectangles with coordinates within the range $1 \sim n$, calculate the sum of the $k$-th power of the number of points inside each rectangle.

Formally, calculate:

$$ \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 $$

Input

The first line contains two positive integers $n$ and $k$.

The second line contains $n$ positive integers, representing the permutation $p$.

Output

Output the answer. Since the answer may be large, output it modulo $998244353$.

Examples

Input 1

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

Output 1

4948

Input 2

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

Output 2

16614

Input 3

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

Output 3

74224

Subtasks

For $100\%$ of the data, $1\le n\le 10^5$ and $1\le k\le 3$.