D - Swap Permutation Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

(1,2,\dots,N) の順列 P=(P_1,P_2,\dots,P_N) が与えられます。これから以下の操作を M 回行います。

  • 1 \le i < j \le N を満たす整数の組 (i,j) を選び、P_i と P_j を入れ替える。

操作列は \left(\frac{N(N-1)}{2}\right)^M 通りありますが、その全てに対する操作終了時の \sum_{i=1}^{N-1} |P_i - P_{i+1}| の総和を 998244353 で割ったあまりを求めてください。

制約

  • 2 \le N \le 2 \times 10^5
  • 1 \le M \le 2 \times 10^5
  • (P_1,P_2,\dots,P_N) は (1,2,\dots,N) の順列

入力

入力は以下の形式で標準入力から与えられる。

N M
P_1 P_2 \dots P_N

出力

答えを出力せよ。

入力例 1

3 1
1 3 2

出力例 1

8

操作列としてあり得るものは以下の 3 通りです。

  • (i,j) = (1,2) を選ぶ。P=(3,1,2) となる。
  • (i,j) = (1,3) を選ぶ。P=(2,3,1) となる。
  • (i,j) = (2,3) を選ぶ。P=(1,2,3) となる。

それぞれの \sum_{i=1}^{N-1} |P_i - P_{i+1}| は 3,3,2 です。よって答えは 3 + 3 + 2 = 8 です。

入力例 2

2 5
2 1

出力例 2

1

入力例 3

5 2
3 5 1 4 2

出力例 3

833

入力例 4

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

出力例 4

203984325

Score: 700 points

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