Tokitsukaze and Permutations
Contest: Codeforces Round 789 (Div. 1)
Difficulty rating: 2500
Tags: dp, math

Tokitsukaze has a permutation $$$p$$$. She performed the following operation to $$$p$$$ exactly $$$k$$$ times: in one operation, for each $$$i$$$ from $$$1$$$ to $$$n - 1$$$ in order, if $$$p_i$$$ > $$$p_{i+1}$$$, swap $$$p_i$$$, $$$p_{i+1}$$$. After exactly $$$k$$$ times of operations, Tokitsukaze got a new sequence $$$a$$$, obviously the sequence $$$a$$$ is also a permutation.

After that, Tokitsukaze wrote down the value sequence $$$v$$$ of $$$a$$$ on paper. Denote the value sequence $$$v$$$ of the permutation $$$a$$$ of length $$$n$$$ as $$$v_i=\sum_{j=1}^{i-1}[a_i < a_j]$$$, where the value of $$$[a_i < a_j]$$$ define as if $$$a_i < a_j$$$, the value is $$$1$$$, otherwise is $$$0$$$ (in other words, $$$v_i$$$ is equal to the number of elements greater than $$$a_i$$$ that are to the left of position $$$i$$$). Then Tokitsukaze went out to work.

There are three naughty cats in Tokitsukaze's house. When she came home, she found the paper with the value sequence $$$v$$$ to be bitten out by the cats, leaving several holes, so that the value of some positions could not be seen clearly. She forgot what the original permutation $$$p$$$ was. She wants to know how many different permutations $$$p$$$ there are, so that the value sequence $$$v$$$ of the new permutation $$$a$$$ after exactly $$$k$$$ operations is the same as the $$$v$$$ written on the paper (not taking into account the unclear positions).

Since the answer may be too large, print it modulo $$$998\,244\,353$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. Each test case consists of two lines.

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^6$$$; $$$0 \leq k \leq n-1$$$) — the length of the permutation and the exactly number of operations.

The second line contains $$$n$$$ integers $$$v_1, v_2, \dots, v_n$$$ ($$$-1 \leq v_i \leq i-1$$$) — the value sequence $$$v$$$. $$$v_i = -1$$$ means the $$$i$$$-th position of $$$v$$$ can't be seen clearly.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, print a single integer — the number of different permutations modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, only permutation $$$p=[5,4,3,2,1]$$$ satisfies the constraint condition.

In the second test case, there are $$$6$$$ permutations satisfying the constraint condition, which are:

- $$$[3,4,5,2,1]$$$ $$$\rightarrow$$$ $$$[3,4,2,1,5]$$$ $$$\rightarrow$$$ $$$[3,2,1,4,5]$$$
- $$$[3,5,4,2,1]$$$ $$$\rightarrow$$$ $$$[3,4,2,1,5]$$$ $$$\rightarrow$$$ $$$[3,2,1,4,5]$$$
- $$$[4,3,5,2,1]$$$ $$$\rightarrow$$$ $$$[3,4,2,1,5]$$$ $$$\rightarrow$$$ $$$[3,2,1,4,5]$$$
- $$$[4,5,3,2,1]$$$ $$$\rightarrow$$$ $$$[4,3,2,1,5]$$$ $$$\rightarrow$$$ $$$[3,2,1,4,5]$$$
- $$$[5,3,4,2,1]$$$ $$$\rightarrow$$$ $$$[3,4,2,1,5]$$$ $$$\rightarrow$$$ $$$[3,2,1,4,5]$$$
- $$$[5,4,3,2,1]$$$ $$$\rightarrow$$$ $$$[4,3,2,1,5]$$$ $$$\rightarrow$$$ $$$[3,2,1,4,5]$$$

So after exactly $$$2$$$ times of swap they will all become $$$a=[3,2,1,4,5]$$$, whose value sequence is $$$v=[0,1,2,0,0]$$$.

Example input:
3
5 0
0 1 2 3 4
5 2
-1 1 2 0 0
5 2
0 1 1 0 0

Example output:
1
6
6

Editorial:
Consider finding out the relationship between sequence $$$v$$$ and permutation $$$p$$$. It can be observed that the permutation $$$p$$$ have bijective relationship with sequence $$$c$$$. That is to say, sequence $$$c$$$ will only correspond to one permutation $$$p$$$, as it can be proved:
Let $$$S=\{1,2,\ldots,n\}$$$, and find that the last number can be determined through $$$c_n$$$, because there is no number after this position. We observe that $$$p_n$$$ is the $$$(c_n+1)$$$ largest number in $$$S$$$, then delete $$$p_n$$$ from $$$S$$$, we can get $$$p_{n - 1}$$$. So repeat the process, we can get the whole permutation.
Consider counting $$$v$$$, we observe that each bubble sort will first make $$$v_i=\max(v_{i}-1,0)$$$, then the whole $$$v$$$ moves left, $$$v_1$$$ is directly covered, $$$v_n$$$ is set to $$$0$$$. Because each valued $$$v_i$$$ is preceded by a number larger than the current position, then it will definitely be exchanged and moved forward, $$$v_i$$$ minus $$$1$$$.
For example, if the current $$$v=[0,0,2,1,1]$$$, after once bubble sort, $$$v=[0,1,0,0,0]$$$.
To avoid confusion, the $$$V$$$ array below is the $$$v$$$ in the input. It's easy to count after knowing the above conclusion.
For the position $$$i(i\le k)$$$, it can be observed that after $$$k$$$ times of bubble sort , it is directly covered, so just multiply the answer by $$$\prod_{i=1}^k i$$$.
For the position $$$i(k\lt i \le n)$$$, if $$$V_{i-k}\ne -1$$$, then obviously $$$v_i$$$ is uniquely determined; If $$$V_{i-k}=-1$$$, then $$$v_i$$$ has $$$i$$$ possible values, multiply the answer by $$$i$$$; If $$$V_{i-k}=0$$$, then $$$v_i-k\le 0$$$, multiply the answer by $$$k+1$$$.
Note that for the position $$$i(i\ge n-k+1)$$$, $$$V_i$$$ should be $$$0$$$ or $$$-1$$$, otherwise the answer must be $$$0 $$$.
Complexity:$$$\mathcal{O}(n)$$$.