Дана перестановка $p$. Для каждого $i$ мы размещаем точку $(i, p_i)$ на плоскости. Для всех $\left(\frac{n(n+1)}{2}\right)^2$ прямоугольников, координаты которых лежат в пределах от $1$ до $n$, найдите сумму $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
Выходные данные
4948
Пример 2
Входные данные
10 2 2 1 10 3 5 9 4 7 6 8
Выходные данные
16614
Пример 3
Входные данные
10 3 2 1 10 3 5 9 4 7 6 8
Выходные данные
74224
Подзадачи
Для $100\%$ данных гарантируется $1\le n\le 10^5; 1\le k\le 3$.
| Номер теста | $n=$ | $k=$ |
|---|---|---|
| $1$ | $50$ | $3$ |
| $2$ | $300$ | $1$ |
| $3$ | $2$ | |
| $4$ | $3$ | |
| $5$ | $3000$ | $1$ |
| $6$ | $2$ | |
| $7$ | $3$ | |
| $8$ | $10^5$ | $1$ |
| $9$ | $2$ | |
| $10$ | $3$ |