Score: $700$ points

问题陈述

给定一个排列 ( P = (P_1, P_2, \dots, P_N) )，它是 ( (1, 2, \dots, N) ) 的一个排列。你需要执行以下操作 ( M ) 次：

• 选择一对整数 ( (i, j) )，使得 ( 1 \le i < j \le N )，并且交换 ( P_i ) 和 ( P_j )。

有 ( \left(\frac{N(N-1)}{2}\right)^M ) 种可能的操作序列。对于每一种序列，在所有操作之后考虑值 ( \sum_{i=1}^{N-1} |P_i - P_{i+1}| )。找出所有这些值的总和，对 ( 998244353 ) 取模。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given a permutation $P=(P_1,P_2,\dots,P_N)$ of $(1,2,\dots,N)$. You will perform the following operation $M$ times:

• Choose a pair of integers $(i, j)$ such that $1 \le i < j \le N$, and swap $P_i$ and $P_j$.

There are $\left(\frac{N(N-1)}{2}\right)^M$ possible sequences of operations. For each of them, consider the value $\sum_{i=1}^{N-1} |P_i - P_{i+1}|$ after all the operations. Find the sum, modulo $998244353$, of all those values.

Constraints

• $2 \le N \le 2 \times 10^5$
• $1 \le M \le 2 \times 10^5$
• $(P_1,P_2,\dots,P_N)$ is a permutation of $(1,2,\dots,N)$.

Input

The input is given from Standard Input in the following format:

$N$ $M$

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

Output

Print the answer.

Sample Input 1

3 1
1 3 2

Sample Output 1

8

There are three possible sequences of operations:

• Choose $(i,j) = (1,2)$, making $P=(3,1,2)$.
• Choose $(i,j) = (1,3)$, making $P=(2,3,1)$.
• Choose $(i,j) = (2,3)$, making $P=(1,2,3)$.

The values of $\sum_{i=1}^{N-1} |P_i - P_{i+1}|$ for these cases are $3$, $3$, $2$, respectively. Thus, the answer is $3 + 3 + 2 = 8$.

Sample Input 2

2 5
2 1

Sample Output 2

1

Sample Input 3

5 2
3 5 1 4 2

Sample Output 3

833

Sample Input 4

20 24
14 1 20 6 11 3 19 2 7 10 9 18 13 12 17 8 15 5 4 16

Sample Output 4

203984325