Problem Description

Given integers $ N,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 (including zero):

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

Find the number of possible permutations of $ P $ after the operations, modulo $ 998244353 $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ P_1 $ $ P_2 $ $\cdots$ $ P_N $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

3 3
2 3 1

Sample Output #1

2

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

Notes/Hints

Constraints

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

Sample Explanation 1

In this example, the only possible operation is with $ i=1 $. After one operation, the values of the largest element ($ =P_2=3 $) and the second largest element ($ =P_1=2 $) among $ P_1,P_2,P_3 $ are swapped, resulting in $ P=(3,2,1) $. Performing the operation again results in $ P=(2,3,1) $. Therefore, the possible permutations after the operations are $ P=(2,3,1),(3,2,1) $, totaling 2.

见题面 Input 部分

见题面 Output 部分