题目描述

$(1,2,\dots,N)$ の順列 $Q=(Q_1,Q_2,\dots,Q_N)$ に対する以下の値を $f(Q)$ と置きます。

$1\ \le\ i\ かつ\ Q_i\ >\ Q_j$ を満たす整数の組 $(i,j)$ 全てに対する $j-i$ の総和

$(1,2,\dots,N)$ の順列 $P=(P_1,P_2,\dots,P_N)$ が与えられます。

以下の操作を $M$ 回繰り返します。

• $1\ \le\ i\ \le\ j\ \le\ N$ を満たす整数の組 $(i,j)$ を選ぶ。$P_i,P_{i+1},\dots,P_j$ を反転する。厳密には、$P_i,P_{i+1},\dots,P_j$ の値を $P_j,P_{j-1},\dots,P_i$ の値に同時に置き換える。

操作を行う方法は $\left(\frac{N(N+1)}{2}\right)^{M}$ 通りありますが、その全てに対して操作終了後の $f(P)$ を求めたとします。

これらの $\left(\frac{N(N+1)}{2}\right)^{M}$ 個の値の総和を $998244353$ で割ったあまりを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $P_1$ $P_2$ $\dots$ $P_N$

输出格式

答えを $1$ 行に出力せよ。

题目大意

给定 $n,m$ 两个正整数和一个 $n$ 的排列 $P$。重复进行如下操作 $m$ 次：

• 选定 $1\le i\le j\le n$，并将 $P_i,P_{i+1},..,P_j$ 翻转。

对于所有 $(\frac{n(n+1)}{2})^m$ 种方案，计算 $\sum_{i<j}[P_i>P_j](j-i)$ 的值的和。

2 1
1 2

1

3 2
3 2 1

90

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

543960046

提示

制約

• $1\ \le\ N,M\ \le\ 2\ \times\ 10^5$
• $(P_1,P_2,\dots,P_N)$ は $(1,2,\dots,N)$ の順列である。

Sample Explanation 1

あり得る操作は以下の $3$ 通りです。 - $(i,j)=(1,1)$ を選ぶ。$P=(1,2)$ となる。$f(P)=0$ である。 - $(i,j)=(1,2)$ を選ぶ。$P=(2,1)$ となる。$f(P)=1$ である。 - $(i,j)=(2,2)$ を選ぶ。$P=(1,2)$ となる。$f(P)=0$ である。 よって、答えは $0+1+0=1$ です。