题目描述

给定一个 $(1, 2, \dots, N)$ 的排列 $p_1, p_2, \dots, p_N$ 和一个整数 $K$。maroon 君会对 $i = 1, 2, \dots, N - K + 1$ 依次进行如下操作：

• 将 $p_i, p_{i+1}, \dots, p_{i+K-1}$ 这 $K$ 个数进行等概率随机打乱。

请你求出所有操作结束后，数列的逆序对数的期望值，并将结果对 $998244353$ 取模后输出。

更准确地说，期望值可以表示为一个最简分数 $\frac{P}{Q}$，并且一定存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353},\ 0 \leq R < 998244353$。请输出这个 $R$。

另外，数列 $a_1, a_2, \dots, a_N$ 的逆序对数定义为满足 $i < j,\ a_i > a_j$ 的有序对 $(i, j)$ 的个数。

输入格式

$N$ $K$ $p_1$ $p_2$ ... $p_N$

输出格式

请输出期望值对 $998244353$ 取模后的结果。

输入输出样例 #1

输入 #1

3 2
1 2 3

输出 #1

1

输入输出样例 #2

输入 #2

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

输出 #2

164091855

说明/提示

限制条件

• $2 \leq N \leq 200,\!000$
• $2 \leq K \leq N$
• $(p_1, p_2, \dots, p_N)$ 是 $(1, 2, \dots, N)$ 的一个排列
• 输入的所有数均为整数。

样例解释 1

最终的数列可能为 $(1, 2, 3)$、$(2, 1, 3)$、$(1, 3, 2)$、$(2, 3, 1)$，它们出现的概率均为 $\frac{1}{4}$。这些数列的逆序对数分别为 $0, 1, 1, 2$，因此期望值为 $1$。