题目描述

对于 $(1,2,\dots,N)$ 的一个排列 $Q=(Q_1,Q_2,\dots,Q_N)$，定义如下的值为 $f(Q)$：

对于所有满足 $1\leq i < j \leq n$ 且 $Q_i > Q_j$ 的整数对 $(i,j)$，将所有 $j-i$ 的和记为 $f(Q)$。

给定 $(1,2,\dots,N)$ 的一个排列 $P=(P_1,P_2,\dots,P_N)$。

你需要重复以下操作 $M$ 次：

• 选择满足 $1\leq i\leq j\leq 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)$，你需要求它们的总和，并对 $998244353$ 取模。

输入格式

输入以如下格式从标准输入给出。

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

输出格式

输出一行，表示答案。

样例 1

输入

2 1
1 2

输出

1

样例 2

输入

3 2
3 2 1

输出

90

样例 3

输入

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

输出

543960046

说明/提示

限制条件

• $1\leq N,M\leq 2\times 10^5$
• $(P_1,P_2,\dots,P_N)$ 是 $(1,2,\dots,N)$ 的一个排列。

样例解释 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$。

由 ChatGPT 4.1 翻译