配点 : $900$ 点

問題文

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

$$1 \le i < j \le N$$$$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$ で割ったあまりを求めてください。

制約

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

入力

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

$N$ $M$

$P_1$ $P_2$ $\dots$ $P_N$

出力

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

2 1
1 2

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$ です。

3 2
3 2 1

90

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

543960046