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 \lt a_j]$, where the value of $[a_i \lt a_j]$ define as if $a_i \lt 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$.

Tokitsukaze 有一个排列 $p$。她对 $p$ 恰好执行了 $k$ 次如下操作：每次操作中，按 $i$ 从 $1$ 到 $n - 1$ 的顺序，对每个 $i$，若 $p_i > p_{i+1}$，则交换 $p_i$ 与 $p_{i+1}$。经过恰好 $k$ 次操作后，Tokitsukaze 得到了一个新的序列 $a$；显然，序列 $a$ 也是一个排列。

之后，Tokitsukaze 将排列 $a$ 的“值序列”$v$ 记录在纸上。长度为 $n$ 的排列 $a$ 的值序列 $v$ 定义为：

$$v_i = \sum_{j=1}^{i-1}[a_i < a_j],$$

其中 $[a_i < a_j]$ 是一个指示函数：当 $a_i < a_j$ 时值为 $1$，否则为 $0$（换言之，$v_i$ 等于位于位置 $i$ 左侧且大于 $a_i$ 的元素个数）。随后，Tokitsukaze 出门工作。

Tokitsukaze 家中有三只淘气的猫。她回家后发现记录值序列 $v$ 的纸被猫咬出了若干个洞，导致某些位置上的数值变得模糊不清。她已记不得原始排列 $p$ 是什么了。她想知道：有多少个不同的排列 $p$，使得在恰好执行 $k$ 次上述操作后得到的新排列 $a$ 所对应的值序列 $v$，与纸上所记录的 $v$（忽略那些模糊不清的位置）完全一致？

由于答案可能非常大，请输出其对 $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$.

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。每个测试用例由两行组成。

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 10^6$；$0 \leq k \leq n-1$），分别表示排列的长度以及恰好执行的操作次数。

第二行包含 $n$ 个整数 $v_1, v_2, \dots, v_n$（$-1 \leq v_i \leq i-1$），即值序列 $v$。其中 $v_i = -1$ 表示 $v$ 的第 $i$ 个位置模糊不清，无法辨认。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

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

对于每个测试用例，输出一个整数——不同排列的数量对 $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]$.

在第一个测试用例中，仅有排列 $p=[5,4,3,2,1]$ 满足约束条件。

在第二个测试用例中，共有 $6$ 个满足约束条件的排列，它们是：

• $[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]$

因此，经过恰好 $2$ 次交换后，它们均变为 $a=[3,2,1,4,5]$，其值序列为 $v=[0,1,2,0,0]$。