Dana jest permutacja $p$. Dla każdego $i$ umieszczamy punkt $(i, p_i)$ na płaszczyźnie. Dla wszystkich $\left(\frac {n(n+1)}{2}\right)^2$ prostokątów, których współrzędne mieszczą się w zakresie od $1$ do $n$, oblicz sumę $k$-tych potęg liczby punktów znajdujących się wewnątrz każdego z tych prostokątów.
Formalnie, należy obliczyć:
$$ \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 $$
Wejście
W pierwszej linii znajdują się dwie dodatnie liczby całkowite $n, k$.
W drugiej linii znajduje się $n$ dodatnich liczb całkowitych tworzących permutację $p$.
Wyjście
Wypisz wynik. Ponieważ wynik może być bardzo duży, wypisz go modulo $998244353$.
Przykład
Przykład 1
Wejście
10 1 2 1 10 3 5 9 4 7 6 8
Wyjście
4948
Przykład 2
Wejście
10 2 2 1 10 3 5 9 4 7 6 8
Wyjście
16614
Przykład 3
Wejście
10 3 2 1 10 3 5 9 4 7 6 8
Wyjście
74224
Podzadania
W poniższej tabeli przedstawiono ograniczenia dla poszczególnych podzadań:
| Numer testu | $n$ | $k$ |
|---|---|---|
| $1$ | $50$ | $3$ |
| $2$ | $300$ | $1$ |
| $3$ | $300$ | $2$ |
| $4$ | $300$ | $3$ |
| $5$ | $3000$ | $1$ |
| $6$ | $3000$ | $2$ |
| $7$ | $3000$ | $3$ |
| $8$ | $10^5$ | $1$ |
| $9$ | $10^5$ | $2$ |
| $10$ | $10^5$ | $3$ |