CF1677D.Tokitsukaze and Permutations

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$ .

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$ .

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

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]$ .