B - The Greatest Two Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 1500

問題文

整数 N,K(1,2,\cdots,N) の順列 P=(P_1,P_2,\cdots,P_N) が与えられます.

あなたは以下の操作を好きな回数 (0 回でもよい) 行うことができます.

  • 整数 i (1 \leq i \leq N-K+1) を選ぶ. P_i,P_{i+1},\cdots,P_{i+K-1} の中で 1 番目に大きい要素と 2 番目に大きい要素の値を入れ替える.

操作後の P としてあり得る順列の個数を 998244353 で割ったあまりを求めてください.

制約

  • 2 \leq K \leq N \leq 250000
  • (P_1,P_2,\cdots,P_N)(1,2,\cdots,N) の順列である.
  • 入力される値はすべて整数.

入力

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

N K
P_1 P_2 \cdots P_N

出力

答えを出力せよ.


入力例 1

3 3
2 3 1

出力例 1

2

この例では可能な操作は i=1 のみです.

1 回操作すると,P_1,P_2,P_3 の中で 1 番目に大きい要素 (=P_2=3)と 2 番目に大きい要素 (=P_1=2) の値が入れ替わり,P=(3,2,1) になります. さらにもう一度操作すると,P=(2,3,1) になります.

よって,操作後の順列としてあり得るのは P=(2,3,1),(3,2,1)2 つです.


入力例 2

3 2
1 3 2

出力例 2

6

入力例 3

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

出力例 3

144

入力例 4

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

出力例 4

1451520

Score : 1500 points

Problem Statement

You are given integers N and K, and a permutation P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N).

You can perform the following operation any number of times, possibly zero.

  • Choose an integer i (1 \leq i \leq N-K+1). Swap the values of the two greatest elements among P_i,P_{i+1},\cdots,P_{i+K-1}.

Find the number, modulo 998244353, of permutations that P can be after your operations.

Constraints

  • 2 \leq K \leq N \leq 250000
  • (P_1,P_2,\cdots,P_N) is a permutation of (1,2,\cdots,N).
  • All input values are integers.

Input

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

N K
P_1 P_2 \cdots P_N

Output

Print the answer.


Sample Input 1

3 3
2 3 1

Sample Output 1

2

In this case, the operation can only be performed with i=1.

After one operation, the two greatest elements among P_1,P_2,P_3, which are P_2=3 and P_1=2, have their values swapped, and you have P=(3,2,1). After one more operation, you have P=(2,3,1).

Thus, there are two permutations, P=(2,3,1),(3,2,1), that P can be after your operations.


Sample Input 2

3 2
1 3 2

Sample Output 2

6

Sample Input 3

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

Sample Output 3

144

Sample Input 4

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

Sample Output 4

1451520