Description

Given integers $n, k$ and an $n$-th permutation $\pi'$, ask how many permutations $\pi$ satisfy that there are exactly $k$ positions $i$ such that $1 \le i \le n$ and $\pi_i < \pi_{\pi'_i}$. Output the answer modulo $998244353$.

Input Format

The first line contains two integers $n, k$.

The second line contains $n$ positive integers, representing $\pi'$.

Output Format

Output one line containing one non-negative integer, representing the number of permutations $\pi$ that satisfy the condition.

5 0
1 2 3 4 5

120

5 1
2 3 4 5 1

5

5 2
2 4 5 1 3

60

Hint

Sample Explanation

For the first sample, $\pi_i$ cannot be less than $\pi_i$, so the condition must always be satisfied. Therefore, the answer is $5! = 120$.

For the second sample, there are the following $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.

Constraints

For $20\%$ of the testdata, $n \le 10$.

For $40\%$ of the testdata, $n \le 3 \times 10^2$.

For $60\%$ of the testdata, $n \le 10^3$.

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

For $100\%$ of the testdata, $1 \le n \le 2 \times 10^5$, $0 \le k \le n$.

Translated by ChatGPT 5