题目描述

给定一个排列 $p_1, p_2, \\dots, p_N$，其中 $p_i$ 是 $(1, 2, ..., N)$ 的一个排列，以及一个整数 $K$。Maroon 按照以下顺序执行操作 $i = 1, 2, \\dots, N - K + 1$：

• 将 $p_i, p_{i + 1}, \\dots, p_{i + K - 1}$ 均匀随机地洗牌。

计算在执行所有操作后，序列的逆序数的期望值，并将其模 $998244353$ 后打印出来。

更具体地说，根据问题的约束条件，可以证明期望值始终是一个有理数，可以表示为一个不可约分数 $\\frac{P}{Q}$，满足 $R \\times Q \\equiv P \\pmod{998244353}, 0 \\leq R < 998244353$，其中 $R$ 是唯一确定的。打印出这个 $R$。

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

约束条件

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

输入

输入以以下格式从标准输入给出：

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

输出

打印出模 $998244353$ 后的期望值。

样例输入 1

3 2
1 2 3

样例输出 1

1

最终序列可能是 $(1, 2, 3)$、$(2, 1, 3)$、$(1, 3, 2)$、$(2, 3, 1)$ 中的一个，每个概率都是 $\\frac{1}{4}$。它们的逆序数分别为 $0, 1, 1, 2$，所以期望值为 $1$。

样例输入 2

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

样例输出 2

164091855