Problem Description

Given integers \( n, k \) and an \( n \)-order permutation \( \pi' \), how many permutations \( \pi \) satisfy exactly \( k \) positions \( i \) such that \( 1 \le i \le n \) and \( \pi_i < \pi_{\pi'_i} \). The answer should be taken modulo \( 998244353 \).

Input Format

The first line contains two integers \( n \) and \( k \).

The second line contains \( n \) positive integers representing \( \pi' \).

Output Format

A single line containing a non-negative integer, representing the number of permutations \( \pi \) that meet the conditions.

Sample Input and Output

Sample Input #1

5 0
1 2 3 4 5

Sample Output #1

120

Sample Input #2

5 1
2 3 4 5 1

Sample Output #2

5

Sample Input #3

5 2
2 4 5 1 3

Sample Output #3

60

Notes

Sample Explanation

For the first sample, \( \pi_i \) cannot be less than \( \pi_i \), so it always satisfies the condition, and the answer is \( 5! = 120 \).

For the second sample, there are 5 permutations \( \pi \) that satisfy the condition:

1. \( 12345 \);
2. \( 23451 \);
3. \( 34512 \);
4. \( 45123 \);
5. \( 51234 \).

For the third sample, no explanation is provided.

Data Range

For 20% of the data, \( n \le 10 \).

For 40% of the data, \( n \le 3 \times 10^2 \).

For 60% of the data, \( n \le 10^3 \).

For another 20% of the data, it is guaranteed that \( \pi'_i = i \bmod n + 1 \) (for \( 1 \le i \le n \)).

For 100% of the data, \( 1 \le n \le 2 \times 10^5 \) and \( 0 \le k \le n \).

见题面 Input 部分

见题面 Output 部分