AT_abc380_g [ABC380G] Another Shuffle Window

[problemUrl]: https://atcoder.jp/contests/abc380/tasks/abc380_g $ (1,2,\dots,N) $ の順列 $ P $ と整数 $ K $ が与えられます。 順列 $ P $ に以下の操作を行った後の転倒数の期待値を $ \text{mod}\ 998244353 $ で求めてください。 - まず、整数 $ i $ を $ 1 $ 以上 $ N-K+1 $ 以下の整数の中から一様ランダムに選択する。 - その後、 $ P_i,P_{i+1},\dots,P_{i+K-1} $ を一様ランダムにシャッフルする。 転倒数とは? 数列 $ (A_1,A_2,\dots,A_N) $ の転倒数とは、 $ 1\ \le\ i\ かつ\ A_i\ >\ A_j $ を満たす整数組 $ (i,j) $ の個数を指します。 期待値 $ \text{mod}\ 998244353 $ とは? 求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 $ \frac{P}{Q} $ で表した時、$ Q\ \not\ \equiv\ 0\ \pmod{998244353} $ となることも証明できます。 よって、$ R\ \times\ Q\ \equiv\ P\ \pmod{998244353},\ 0\ \leq\ R\ を満たす整数\ R $ が一意に定まります。 この $ R $ を答えてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ P_1 $ $ P_2 $ $ \dots $ $ P_N $

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

### 制約 - 入力は全て整数 - $ 1\ \le\ K\ \le\ N\ \le\ 2\ \times\ 10^5 $ - $ P $ は $ (1,2,\dots,N) $ の順列 ### Sample Explanation 1 操作によって、順列 $ P $ は以下のように変化します。 - $ (1,4,2,3) $ ... 確率 $ 1/2 $ - $ (4,1,2,3) $ ... 確率 $ 1/6 $ - $ (1,2,4,3) $ ... 確率 $ 1/6 $ - $ (1,4,3,2) $ ... 確率 $ 1/6 $ 転倒数の期待値は、 $ \displaystyle\ 2\ \times\ \frac{1}{2}\ +\ 3\ \times\ \frac{1}{6}\ +\ 1\ \times\ \frac{1}{6}\ +\ 3\ \times\ \frac{1}{6}\ =\ \frac{13}{6} $ となります。 $ \displaystyle\ \frac{13}{6} $ を $ \text{mod}\ 998244353 $ で表現すると $ 166374061 $ となるので、これを出力してください。